题目大意
求1~N 中素数的个数。
题目分析
线性筛肯定是要爆空间时间的,但是显然我们可以不筛$2$的倍数,然后将时间空间卡进限制。
代码
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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| #include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num; } int Prime[6000005]; bool vst[50000005]; int n,cnt=0; void Prime_Table(int n) { for(int i=3; i<=n; i+=2) { if(vst[(i-1)/2]==0)Prime[++cnt]=i; for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) { vst[(i*Prime[j]-1)/2]=1; if(i%Prime[j]==0)break; } } } int main() { n=Get_Int(); if(n==1) { puts("0"); return 0; } Prime_Table(n); printf("%d\n",cnt+1); return 0; }
|