Python :

# coding=utf-8
def construct_plist():
    MAX = 10**6+1
    fl = [0 for _ in range(MAX)]
    prime_list = []
    for i in range(2, MAX):
        if fl[i]:
            continue
        prime_list.append(i)
        for j in range(i, MAX, i):
            fl[j] = 1
    return prime_list

prime_list = construct_plist()
N = int(input())
ANS = 0
LEN = len(prime_list)
q = LEN - 1

for i in range(LEN):
    while i < q and prime_list[i]*prime_list[q]**3 > N:
        q -= 1
    if i >= q:
        break
    ANS += q - i

print(ANS)

首先根据题意我们知道，因为 $1 \le k \le N$ ，所以 $k$ 最大不超过 $10^{18}$ 。 然后分析 $k$ 的组成，可以发现需要用到的最大质数不超过 $\sqrt[3]{k}$ ，即 $10^6$ 。那么直接预处理出 $10^6$ 范围内的质数，然后计算即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
LL primes[N],cnt;bool st[N];

inline void get_P(LL x)
{
    for(LL i = 2;i <= x;i++)
    {
        if(!st[i]){primes[++cnt] = i;}
        for(int j = 1;j <= cnt && primes[j] * i <= x;j++)
        {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
    return ;
}

inline bool check(LL x,LL lm) {return x <= cnt && primes[x] * primes[x] * primes[x] <= lm;}
inline LL v(LL x){return x * x * x;}

int main()
{
    LL n;cin >> n;
    LL res = 0;
    get_P(1000000);
    for(LL i = 1;check(i,n);i++)
        for(int j=1;j<=cnt&&primes[j]<primes[i]&&primes[j]*v(primes[i])<=n;j++)
            res++;
    cout << res << endl;
    return 0;
}