【算法】Eratosthenes筛选法与欧拉筛选法求素数

港控/mmm° 2022-04-01 04:12 277阅读 0赞

#### Eratosthenes筛法 ####

###### 1.原理 ######

一个合数可以分成几个素数的和，如果把素数(最初只知道2)的倍数全都去掉，剩下的就都是素数了

###### 2.思路分析 ######

1.  去除0，1(既不是素数又不是合数)
2.  找到队列中最小的素数，删除其倍数

![在这里插入图片描述][20181229103300441.gif]

###### 3.代码实现（只给出了函数，未写主函数） ######

用一数组存这一列数，数组的标号即为数字，值1表示为素数，值0表示不为素数

void sieveofe(int p[], int n)   //将数组p[],和数组的最大范围n,输入
    { 
        int i, j;
     
        p[0] = 0;
        p[1] = 0;
        p[2] = 1;
        // 初始化
        
        for(i = 3; i <= n; i++) 
    	{ 
            p[i++] = 1;
            p[i] = 0;
        }
        //除了2，其余偶数都是合数，先去除偶数
        
        int max = sqrt(n);
        for(i = 3; i <= max; i++)     //只需要判断到sqrt(n)
    	{ 
            if(p[i])
    		{ 
                for(j = i * i; j < n; j += i)    
                    p[j] = 0;
       //进行筛选，从i*i开始，如对素数3，从3*3开始，不需要从3*2开始，因为对素数2，2*3已经筛去
            }
        }
    }

--------------------

#### 欧拉筛法 ####

Eratosthenes筛选法虽然效率高，但是Eratosthenes筛选法做了许多无用功，一个数会被筛到好几次， 2✖6和3✖4都将12筛去，最后的时间复杂度是O(nloglogn),对于普通素数算法而言已经非常高效了,但欧拉筛选法的时间复杂度仅仅为O(n).

###### 1.原理： ######

**只需要依次筛去由素数为因子的数，剩下的都为素数**  
prime\[ \] 数组中的素数是递增的,当 i 能整除 prime\[ j \] ，那么 i\*prime\[ j+1 \] 这个合数肯定被 prime\[ j \] 乘以某个数筛掉。因为i中含有prime\[ j \]。接下去的素数同理。所以不用筛下去了。

在满足i%prime\[ j \] == 0这个条件之前以及第一次满足改条件时, prime\[ j \] 必定是 prime\[ j \]\*i 的最小因子。

###### 2.代码实现： ######

const int Max = 100002;        
    int Prime[Max];            //用于存素数的值
    int vis[Max];              //用于判断并存所有的素数
    void prime()
    { 
        int num = 0;
        memset(vis,1,sizeof(vis));    //申请空间，将vis数组都赋初值1，即都为素数 
        for(int i = 2; i <= Max; i++)
        { 
            if(vis[i])
                Prime[num++] = i;     //依次存最小的素数
            for(int j = 0; j < num; j++)
            { 
                if (i * Prime[j] > Max)
                    break;
                vis[i * Prime[j]] = 0; //即 i*Prime[j]也不为素数
                if (i % Prime[j] == 0)
                    break;
            }
        }
    }

#### 总结： ####

> 1.  Eratosthenes筛法的第一重循环是用来找素数,然后把素数的倍数标记,而欧拉筛法换了一个角度,第一位是找素数,但是标记的时候用的是所有数
> 2.  欧拉筛选法在数据小的时候不如Eratosthenes筛选法快,反而是数据变大以后，两者差距变得越来越明显,欧拉筛选法明显快于Eratosthenes筛选法
> 3.  欧拉算法是一种空间换时间的算法

###### 参考文章： ######

https://blog.csdn.net/u012102306/article/details/71407105  
https://blog.csdn.net/u012313335/article/details/47663801

[20181229103300441.gif]: /images/20220401/e0ee3abab7094c1aa2e543980272c576.png