rt

#include <bits/stdc++.h>
#define int long long
using namespace std;

bool isp[1000005];
int n, p[100005], cnt[1000005] = {0}, ans = 0;
inline void getpr(int x) {
 memset(isp, 1, sizeof isp);
 isp[1] = false;
 for (int i = 2, cur = 0; i <= x; i++) {
  if (isp[i]) p[++cur] = i;
   for (int j = 1; j <= cur && i * p[j] <= x; j++) {
    isp[i * p[j]] = false;
    if (i % p[j] == 0) break;
   }
 }
}

signed main() {
 cin >> n;
 getpr(1000000);
 for (int i = 1; i <= 1000000; i++)
  if (isp[i]) cnt[i] = cnt[i - 1] + 1;
  else cnt[i] = cnt[i - 1];
 for (int i = 1; p[i] * p[i] * p[i] * p[i] <= n; i++)
  for (int j = i + 2; p[i] * p[i] * p[j] * p[j] <= n; j++)
   ans += max(0LL, min(cnt[min(n / (p[i] * p[i] * p[j] * p[j]), 1000000LL)], j - 1) - i);
 cout << ans << endl;
 return 0;
}

感觉在 $O(\sqrt n\log\log n)$ 左右。