素数筛

一.埃氏筛：

埃氏筛就是利用每个数的合数一定不是素数，用空间换取时间，筛选出一定范围内的素数。（合数：就是某个数的倍数*2，*3......这种）

代码实现：

 1 #include 
 2 #include 
 3 int a[1000000];
 4 int main()
 5 {
 6     int N,i,j;
 7     for(i = 2;i <= 1000000;i++)
 8         if(!a[i]){
 9             for(j = 2;i * j<=1000000;j++) 
10                 a[i * j] = 1;
11         }
12     for(i=2;i<=100;i++)
13         if(a[i]==0)
14             printf("%d\n",i);
15     return 0;
16 }

二：欧拉筛：

欧拉筛也称线性筛，能在O(n)的时间复杂度下筛选出素数，利用空间换取时间，只是在埃氏筛的基础上加了一个判断条件，因为在欧拉筛中会重复把某个数字筛选，造成时间上的浪费，比如说6会被2筛选一遍，也会被3筛选一遍，所以欧拉筛就会把素数存储下来，当某个数碰到的是他的最小素数时，就结束筛选。

 1 #include 
 2 int prime[1000001],is_prime[1000001];
 3 int N,cnt;
 4 int main()
 5 {
 6     for(int i = 2;i <= 1000000;i++){
 7         if(!prime[i])
 8         is_prime[cnt++] = i;
 9         for(int j = 0;j < cnt && i * is_prime[j] <= 1000000;j++){
10             prime[i *is_prime[j]] = 1;
11         if(i % is_prime[j] == 0)
12             break;
13         }
14     }
15     while(~scanf("%d",&N)){
16         for (int i = 2;i <= N;i++)
17             if (!prime[i])
18                 printf("%d\n",i);
19     }
20     return 0;
21 }