1.埃氏筛

时间复杂度O(nloglogn)

  传统的寻找素数的方法时间复杂度很高，当数据规模很大时不再实用，对于OJ通常几百ms或1s的限时，我们通常会采用用空间换时间的方法。

  埃氏筛的思路是在一开始创建一个长度为N+1（N为要查找的最大范围）的数组，数组的下标（从1开始）对应要查找的数字，一开始将数组中的元素通过循环全部赋值为1。另外创建一个数组存放已经找到的素数。

  最小的素数为2，是2的倍数的数都不是素数，因此把这些2的倍数的合数标记为0。4 6 8 10 ……都被标记为0。

  接下来，寻找2之后第一个没有被标记的数（这个数一定是素数），这个数是3，把3放进素数数组。

  是3的倍数的数都不是素数，因此 6 9 12 15……都被标记为0。

  接下来，寻找3之后第一个没有被标记的数（同样的，这个数也一定为素数），这个数是5，把5放进素数数组。

  是5的倍数的数…………

代码实现：

 1 #include<stdio.h>
 2 #define N 10000  //N为最大范围，自定。
 3 int is_prime[N+1];
 4 int primes[N];//素数数组大小自己估计给出
 5 
 6 int main(void){
 7     int count=0;  //用于记录已经找到的素数的个数
 8 
 9     for(int i=2;i<=N;i++)
10         is_prime[i]=1;
11     
12     for(int i=2;i<=N;i++)
13         if(is_prime[i]==1){
14             primes[++count]=i;  
15 
16             //这里我们不用循环和余数来判断是否是某数的倍数
17             for(int j=2*i;j<=N;j+=i)
18                 is_prime[j]=0;
19         }
20       
21     for(int i=1;i<=count;i++)
22     　　printf("%d ",primes[i]);
23         
24      return 0;
25 }

2.欧拉筛（线性筛）：

时间复杂度：O(n)

　　虽然经过优化，埃氏筛（太弱鸡）相比普通方法要快了许多（多??？），但当数据规模再大时，依旧TLE，TLE,TLE（重要的事情说三遍）。

　　通过分析埃氏筛的过程，我们发现6 12被2筛掉之后又被3筛，我们在做重复的工作。

　　欧拉筛的思路是：某合数只被最大非自身质因数筛掉。

   跟踪一下实现过程：

　　　依旧初始化大小为N+1的判定数组（均为1）和一个素数数组。

　　　最小素数为2。从2开始。

　　　2：2未被筛去，把2放进素数数组；遍历素数数组，用2去乘已经得到的素数，并将得到的数筛去（判定数组的对应下标元素标记为0）。2*2=4，筛去4

　　　3：3未被筛去，把3放进素数数组；遍历素数数组，用3去乘已经得到的素数，并将得到的数筛去（判定数组的对应下标元素标记为0）。3*2=6，3*3=9  筛去 6 9

　　　4：4被筛去，不把4放进素数数组；遍历素数数组，用4去乘已经得到的素数，并将得到的数筛去（判定数组的对应下标元素标记为0）。4*2=8 4*3=12 

　　　但是到此我们发现问题了，按照欧拉筛的思路，12不应该被4筛掉而应被6筛掉。

　　　为什么呢？

　　　i%prime[j]==0时，记m=i/prime[j],那么i*prime[j+1]=m*prime[j]*prime[j+1] 说明i*prime[j+1]是prime[j]的倍数。

      因此设i*prime[j+1]=k*prime[j]，由于prime[j+1]>prime[j],因此k>i,所以i*prime[j+1]不应该被i筛掉而应该被k筛掉（若此时k不是最大非自身质因数，则此时的k相当于i，肯定又有下一个更大的k）。

上代码：

#include<stdio.h>
#define N 100000  //N为最大范围，自定。
int is_prime[N+1];
int prime[N];//素数数组大小自己估计给出
 
int main(void){
    int count=0;  //用于记录已经找到的素数的个数
 
    for(int i=2;i<=N;i++)
         is_prime[i]=1;
     
    for(int i=2;i<=N;i++){
        
        if(is_prime[i]==1)
             prime[++count]=i;
         
            //遍历素数数组,用i去乘已经得到的素数      
        for(int j=1;j<=count&&i*prime[j]<=N;j++){ // 注意&&后的条件
            is_prime[i*prime[j]]=0;
            if(i%prime[j]==0)    //******中途结束遍历的条件********关键
                break;
        }
     }
              
    for(int i=1;i<=count;i++)
        printf("%d ",prime[i]);
        
    return 0;
 }

  是不是听起来欧拉筛逼格很高的样子？

  但理解了 {设i*prime[j+1]=k*prime[j]，由于prime[j+1]>prime[j],因此k>i,所以i*prime[j+1]不应该被i筛掉而应该被k筛掉} 这一部分，欧拉筛并不难吧！

素数筛

原文：https://www.cnblogs.com/WhiteThornZzf/p/12329270.html