First, we will show some important observations.

• By the uniqueness of prime factorization, this problem can be rephrased from “counting the number of \(k\) satisfying certain conditions” to “counting the number of pairs \((p, q)\) satisfying certain conditions.”
• Since the constraint of this solution says \(N \le 10^{18}\), it holds that \(q \le 10^6\).
  • This is because, if \(q > 10^6\), then \(pq^3 > 10^{18} \ge N\).
• Moreover, since \(p<q\), we also have \(p \le 10^6\).

From this observation, we will try finding the answer from the list of primes less than \(10^6\) (which can be obtained by Eratosthenes’ sieve).

Here, the following solution is valid.

• First, fix a prime \(p\), which is taken from the prime list.
• Next, find the maximum value \(Q\) of prime \(q\) such that \(pq^3 \le N\).
• Then, for each prime that is greater than \(p\) and less than or equal to \(Q\), it holds that \(pr^3 \le N\). Add the number of such primes to the number of pairs \((p,q)\) satisfying the condition.
  • For example, when \(N=256\), for \(p=2\) we have \(Q=5\); indeed, both \(2 \times 3^3 \le 256\) and \(2 \times 5^3 \le 256\) hold.
• Do the steps above for all primes \(p\) less than \(10^6\).

When finding \(Q\), one way is to do binary search for each \(p\); alternatively, we can find it in a sliding-window-like manner, since as \(p\) increases, \(Q\) monotonically decreases (actually, non-increasing).

The time complexity of this algorithm except for finding prime list is \(O(P)\) or \(O(P \log P)\), where \(P\) is the number of primes less than or equal to \(\sqrt[3]{N}\).

You have to be careful in finding \(pq^3\). Depending on implementation, it may be that \(p,q \approx 10^6\), thus \(pq^3 \approx 10^{24}\). In such case, the product won’t fit in a 64-bit integer. It can be handled with a technique of estimating the rough value with floating point type like double firsthand, and then finding the detailed value. For more details, please refer to function f in the Sample Code.

Sample Code (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;
}