まず、いくつか重要な観察を示します。

• 素因数分解の一意性から、この問題は「条件を満たす \(k\) の個数を数える」問題から「条件を満たす \((p,q)\) の組の個数を数える」問題へと言い換えることができます。
• この問題の制約は \(N \le 10^{18}\) であるので、 \(q \le 10^6\) が成立します。
  
  • なぜなら、もし \(q > 10^6\) であった場合、 \(pq^3 > 10^{18} \ge N\) となってしまいます。
    
• さらに、 \(p<q\) という制約が課されているため、 \(p \le 10^6\) も成立します。

この観察から、 \(10^6\) 以下の素数表 (これは、エラトステネスの篩などを利用して求められます) から答えが求められないか考えます。

ここで、以下の解法が成立します。

• まず、素数表から \(p\) にあたる素数を決め打つ。
• 次に、その \(p\) に対して \(pq^3 \le N\) を満たす素数 \(q\) の最大値 \(Q\) を求める。
• ここで、 \(p\) より大きく \(Q\) 以下である全ての素数 \(r\) について、 \(pr^3 \le N\) となるので、この数を条件を満たす \((p,q)\) の組の個数に加える。
  • 例えば、 \(N=256\) である場合に、 \(p=2\) を決め打った場合 \(Q=5\) であるが、 \(2 \times 3^3 \le 256\) と \(2 \times 5^3 \le 256\) はどちらも成立する。
• 以上の流れを \(10^6\) 以下の全ての素数 \(p\) に対して行う。

\(Q\) を求める部分について、 \(p\) ごとにそれぞれ素数表を二分探索をしてもよいですが、 \(p\) が小さい方から調べていく際に \(Q\) は(広義)単調減少することを利用して尺取り法のような方法で求めることもできます。

素数表を作る部分を除いた計算量は、 \(\sqrt[3]{N}\) 以下の素数の個数を \(P\) とし、 \(O(P)\) または \(O(P \log P)\) です。

\(pq^3\) を求める際にひとつ注意するべきことがあります。実装によっては \(p,q \approx 10^6\) すなわち \(pq^3 \approx 10^{24}\) 程度となる計算を行う必要がある可能性があります。この場合、 64bit 整数でも収まらないので先に double 型などの浮動小数点を扱える実数型で大まかに値の大きさを見積もっておき、その後詳細な値を調べるテクニックがあります。詳しくは実装例の関数 f を参照してください。

実装例(C++):

#include<bits/stdc++.h>

using namespace std;
#define MAXP 1000005

vector<long long> prime_list;
void construct_plist(){
  vector<bool> fl(MAXP,false);
  for(int i=2;i<MAXP;i++){
    if(fl[i]){continue;}
    prime_list.push_back(i);
    for(int j=i;j<MAXP;j+=i){fl[j]=true;}
  }
}

long long f(long long p,long long q){
  double est=1;
  est=(q*q*q);
  est*=p;
  if(est>4e18){return 4e18;}
  return p*q*q*q;
}

int main(){
  construct_plist();
  long long n;
  cin >> n;
  long long res=0;
  int sz=prime_list.size();
  int q=sz-1;
  for(int p=0;p<sz;p++){
    while(p<q && f(prime_list[p],prime_list[q])>n){q--;}
    if(p>=q){break;}
    res+=(q-p);
  }
  cout << res << '\n';
  return 0;
}