快速查找素数
时间限制:1000 ms
| 内存限制:65535 KB
难度:3
- 描述
- 现在给你一个正整数N,要你快速的找出在2.....N这些数里面所有的素数。
- 输入
- 给出一个正整数数N(N<=2000000)
但N为0时结束程序。
测试数据不超过100组 - 输出
- 将2~N范围内所有的素数输出。两个数之间用空格隔开
- 样例输入
-
5 10 11 0
- 样例输出
-
2 3 5 2 3 5 7 2 3 5 7 11
- 来源
- 经典题
- 上传者
- 路过这
-
1 /*快速查找素数*/ 2 #include<stdio.h> 3 #include<math.h> 4 int a[2000001]; 5 int main() 6 { 7 int i,j,n; 8 for(i=2;i<=2000000;i++)/*筛选法求素数*/ 9 { 10 if(a[i]==0) 11 for(j=i+i;j<=2000000;j+=i)//素数的倍数不是素数 12 a[j]=1;//标记 13 } 14 while(scanf("%d",&n)&&n!=0) 15 { 16 printf("2"); 17 for(i=3;i<=n;i++) 18 if(a[i]==0) 19 printf(" %d",i); 20 printf("\n"); 21 } 22 return 0; 23 }