1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| #include<iostream> #include<vector> #include<cmath> using namespace std; const int N = 1e6+10; bool not_prime[N]; int cnt=0; vector<int> primes; void pre(int n) { for(int i=2;i<=n;i++) { if(!not_prime[i]) primes.push_back(i); for(auto pri:primes) { if(1ll*i*pri>n) break; not_prime[pri*i]=true; if(i%pri==0) break; } } } int main() { int n; scanf("%d",&n); pre(n); cout<<primes.size(); }
|