#include using namespace std; typedef long long ll; static const int MAX = 500005; bool isPrime[MAX]; void makePrime() { for (int i = 0; i < MAX; i++) isPrime[i] = true; isPrime[0] = false; isPrime[1] = false; int n = sqrt(MAX); for (int i = 2; i <= n; i++) { if (!isPrime[i]) continue; for (int j = i * 2; j < MAX; j += i) isPrime[j] = false; } } int main() { int N; cin >> N; vector p; makePrime(); for (int i = 2; i <= N; i++) { if (isPrime[i]) p.push_back(i); } int ans = 0; for (int i = 0; i < p.size(); i++) { for (int j = 0; j < p.size(); j++) { ll t = p[i] * p[i] - p[j]; if (t < 1 || t > N) break; if (isPrime[t]) { ans++; } } } cout << ans << endl; return 0; }