hquang0911

include <bits/stdc++.h>

define ll unsigned long long

using namespace std; vector<int> primes; void SieveOfEratosthenes(int n){ bool prime[n + 1]; memset(prime, true, sizeof(prime)); for (int p = 2; p * p <= n; p++) { if (prime[p] == true) { for (int i = p * p; i <= n; i += p) prime[i] = false; } } for (int p = 2; p <= n; p++) if (prime[p]) primes.push_back(p); } int main(){ int n; cin >> n; SieveOfEratosthenes(50001); int ans = 0; int pl = primes.size(); for (int i = 0; i < pl; i++){ ll tmp = pow(primes[i], 8); if (tmp <= n and tmp > 0) ans++; for (int j = i + 1; j < pl; j++){ ll tmp = pow((primes[i]*primes[j]),2); if (tmp <= n and tmp > 0) ans++; } } cout << ans; return 0; }