#include <bits/stdc++.h>
using namespace std;
#define int long long
__int128 prime[2000010], id2;
bool isPrime[4000010];
inline void shai(int n) {
	isPrime[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (!isPrime[i]) {
			prime[++id2] = i;
		}
		for (int j = 1; j <= id2 && i * prime[j] <= n; j++) {
			isPrime[i * prime[j]] = 1;
			if (i % prime[j] == 0)
				break;
		}
	}
}
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n, ans = 0;
	cin >> n;
	shai(sqrtl(n) + 1);
	for (int i = 1; i <= id2; i++) {
//		int k = upper_bound(prime + 1, prime + 1 + id2, n / prime[i]) - prime;
		int l = 1, r = id2;
		while (l < r) {
			int mid = l + r >> 1;
			if (prime[mid] * prime[i] * prime[i] * prime[mid] > n)
				r = mid;
			else
				l = mid + 1;
		}
		if (r < i)
			break;
		if (prime[i] * prime[i] * prime[i] * prime[i] <= sqrtl(n))
			ans++;
		ans += (r - i - 1);
	}
	cout << ans;
	return 0;
}

似乎判了 $p^8$。

WA*13