线性筛
#include<bits/stdc++.h> #define N 1000010 using namespace std; int v[N],p[N]; void pr(int n) { memset(v,0,sizeof(v)); int m=0; for(int i=2;i<=n;i++) { if(v[i]==0) { v[i]=i; p[++m]=i; } for(int j=1;j<=m;j++) { if(p[j]>v[i]||p[j]>n/i)break; v[i*p[j]]=p[j]; } } cout<<m; } int main() { int n; cin>>n; pr(n); return 0; }