#include <bits/stdc++.h>
using namespace std;
int n,cnt;
bool a[10000005];
int main(){
	cin >> n;
	a[0] = a[1] = true;
	for(int i = 2; i <= n; i++){
		for(int j = 2; j <= i; j++){
			if(i * j > n) break;
			if(a[i*j]) continue;
			a[i*j] = true;
			if(i % j == 0) break;
		}
		if(a[i] == false) cnt++;
	}
	cout << cnt << endl;
	return 0;
}

听了欧拉筛写出来的程序

但还是没过qaq