【NYOJ-187】快速查找素数—— 枚举法、筛选法、打表法

快速查找素数

时间限制：1000 ms | 内存限制：65535 KB

难度：3

描述: 现在给你一个正整数N，要你快速的找出在2.....N这些数里面所有的素数。

输入

给出一个正整数数N(N<=2000000)
但N为0时结束程序。
测试数据不超过100组

输出

将2~N范围内所有的素数输出。两个数之间用空格隔开

样例输入

样例输出

　　　　2 3 5

　　　 2 3 5 7

　　　 2 3 5 7 11

【分析】

枚举法：

 1 //根据概念判断:
 2 //如果一个正整数只有两个因子, 1和p，则称p为素数.
 3 //代码:
 4 bool isPrime(int n)
 5 {
 6     if(n < 2) return false;
 7 
 8     for(int i = 2; i < n; ++i)
 9         if(n%i == 0) return false;
10     return true;
11 }
12 //时间复杂度O(n)

 1 //改进, 去掉偶数的判断
 2 //代码:
 3 bool isPrime(int n)
 4 {
 5     if(n < 2) return false;
 6     if(n == 2) return true;
 7     if(n % 2 == 0) return false;
 8     for(int i = 3; i < n; i += 2)
 9         if(n%i == 0) return false;
10     return true;
11 }
12 //时间复杂度O(n/2), 速度提高一倍.

 1 /进一步减少判断的范围
 2 //定理: 如果n不是素数, 则n有满足1<d<=sqrt(n)的一个因子d.
 3 //证明: 如果n不是素数, 则由定义n有一个因子d满足1<d<n.
 4 //如果d大于sqrt(n), 则n/d是满足1<n/d<=sqrt(n)的一个因子.
 5 //代码:
 6 bool isPrime(int n)
 7 {
 8     if(n < 2) return false;
 9     if(n == 2) return true;
10     if(n % 2 == 0) return false;
11     for(int i = 3; i*i <= n; i += 2)
12         if(n%i == 0) return false;
13     return true;
14 }
15 //时间复杂度O(sqrt(n)/2), 速度提高O((n-sqrt(n))/2).

筛选法


　　显然以上的枚举法，不管如何改进都是不能AC的，所以枚举法肯定是行不通的。
　　用筛法求素数的基本思想是：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。剩下的数中选择最小的数是素数，然后去掉它的倍数。依次类推，直到筛子为空时结束。如有：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
　　1不是素数，去掉。剩下的数中2最小，是素数，去掉2的倍数，余下的数是：
　　3 5 7 9 11 13 15 17 19 21 23 25 27 29
　　剩下的数中3最小，是素数，去掉3的倍数，如此下去直到所有的数都被筛完，求出的素数为：
　　2 3 5 7 11 13 17 19 23 29

 1 //筛法判断素数 一
 2 #include<cstdio>
 3 #define MAXN 2000001
 4 int a[MAXN],i,j;
 5 int main(){
 6     int m;
 7     //筛选出二百万内的所有素数
 8     for(i = 2;i <= 2000000;i++){
 9         if(a[i]==0)
10             //利用数组的下标，将i的倍数全部筛掉
11             for(j = i + i;j <= 2000000;j += i)
12                 a[j] = 1;
13     }
14     while(scanf("%d",&m) && m!=0){
15         //从数组中依据下标取出[2,m]内的所有素数
16         for(i = 2;i <= m;i++){
17             if(a[i] == 0){
18                 printf("%d ",i);
19             }
20         }
21         printf("
");
22     }
23     return 0;
24 }

 1 //筛法判断素数 二
 2 #include<cstdio>
 3 #define MAXN 2000001
 4 int a[MAXN],i,j;
 5 int main(){
 6     int m;
 7     while(scanf("%d",&m) == 1 && m!=0){
 8         //m有多大，数组用多大
 9         for(i = 2;i <= m;i++)
10             a[i] =i;
11         //m/2缩小范围
12         for(i = 2;i <= m/2;i++){
13             if(a[i] != 0){
14                 for(j=i+i;j <= m;j += i){
15                     //将i的倍数全部筛掉
16                     a[j] = 0;
17                 }
18             }
19         }
20         for(i = 2;i <= m;i++){
21             if(a[i] != 0) printf("%d
",a[i]);
22         }
23     //    printf("
");
24     }
25     return 0;
26 }

素数打表法

　　正在研究..... 先挖个坑。

　　顺便吐槽NYOJ的服务器。还能再烂么？