一般筛法和快速线性筛法求素数求素数的一点总结

待我称王封你为后i 2022-08-09 12:54 157阅读 0赞

素数总是一个比较常涉及到的内容，掌握求素数的方法是一项基本功。

基本原则就是题目如果只需要判断少量数字是否为素数，直接枚举因子2 。。N^(0.5) ，看看能否整除N。

如果需要判断的次数较多，则先用下面介绍的办法预处理。

##  一般的线性筛法 ##

首先先介绍一般的线性筛法求素数

void make\_prime()  \{

memset(prime, 1, sizeof(prime));

prime\[0\]=false;

prime\[1\]=false;

int N=31700;

for (int i=2;  i<N;  i++)

if (prime\[i\]) \{

primes\[++cnt \]=i;

for (int k=i\*i; k<N; k+=i)

prime\[k\]=false;

return;

这种方法比较好理解，初始时，假设全部都是素数，当找到一个素数时，显然这个素数乘上另外一个数之后都是合数(注意上面的 i\*i ,  比 i\*2 要快点 )，把这些合数都筛掉，即算法名字的由来。

但仔细分析能发现，这种方法会造成重复筛除合数，影响效率。比如10，在i=2的时候，k=2\*15筛了一次；在i=5，k=5\*6 的时候又筛了一次。所以，也就有了快速线性筛法。

# #

## 快速线性筛法    ##

快速线性筛法没有冗余，不会重复筛除一个数，所以“几乎”是线性的，虽然从代码上分析，时间复杂度并不是O(n)。先上代码

首先，先明确一个条件，任何合数都能表示成一系列素数的积。

不管 i 是否是素数，都会执行到“关键处1”，

①如果 i 都是是素数的话，那简单，一个大的素数 i 乘以不大于 i 的素数，这样筛除的数跟之前的是不会重复的。筛出的数都是 N=p1\*p2的形式, p1，p2之间不相等

②如果 i 是合数，此时 i 可以表示成递增素数相乘 i=p1\*p2\*...\*pn, pi都是素数（2<=i<=n），  pi<=pj  ( i<=j )

p1是最小的系数。

根据“关键处2”的定义，当p1==prime\[j\] 的时候，筛除就终止了，也就是说，只能筛出不大于p1的质数\*i。

我们可以直观地举个例子。i=2\*3\*5

此时能筛除 2\*i ,不能筛除 3\*i

如果能筛除3\*i 的话，当 i' 等于 i'=3\*3\*5 时，筛除2\*i' 就和前面重复了。

### 需要证明的东西： ###

1.  一个数会不会被重复筛除。
2.  合数肯定会被干掉。

根据上面红字的条件，现在分析一个数会不会被重复筛除。

设这个数为 x=p1\*p2\*...\*pn, pi都是素数（1<=i<=n)  ,  pi<=pj ( i<=j )

当 i = 2 时，就是上面①的情况，

当 i >2 时， 就是上面②的情况， 对于 i ，第一个能满足筛除 x 的数  y 必然为 y=p2\*p3...\*pn（p2可以与p1相等或不等），而且满足条件的 y 有且只有一个。所以不会重复删除。

证明合数肯定会被干掉？ 用归纳法吧。

类比一个模型，比如说我们要找出 n 中2个不同的数的所有组合 \{ i , j \} ，1<=i<=n, 1<=j<=n,

我们会这么写

for (i=1; i<n; ++i )

for (j=i+1; j<=n; ++j)

.....

我们取 j=i+1 便能保证组合不会重复。快速筛法大概也是这个道理，不过这里比较难理解，没那么直观。

第一种的优化，先判断奇偶。

\#include<iostream>

using namespace std;

const long N = 200000;

long prime\[N\] = \{0\},num\_prime = 0;

int isNotPrime\[N\] = \{1, 1\};

int main()

for(long i = 2 ; i < N ; i ++)

if(! isNotPrime\[i\])

prime\[num\_prime ++\]=i;

//关键处1

for(long j = 0 ; j < num\_prime && i \* prime\[j\] <  N ; j ++)

isNotPrime\[i \* prime\[j\]\] = 1;

if( !(i % prime\[j\] ) )  //关键处2

break;

return 0;

还有一种方法，即第一篇博客说的，实际上是幼拉脱斯展纳筛法，但只是作为学术，不怎么常用

int * eratosthenes(int n){
        
        int a=sqrt(n);
        int* array=new int[n+1];
        for(int i=0;i<n+1;i++){
        
            array[i]=i;
        }
        array[1]=0;
        for(int i=2;i<a+1;i++){
        
            if(array[i]!=0){
        
                for(int j=i+i;j<n+1;j+=i){
        
                    array[j]=0;
                }
            }
        }
        return array;
    }

1.  打印质数的各种算法 [http://coolshell.cn/articles/3738.html][http_coolshell.cn_articles_3738.html]  里面有个用C++模板实现的，纯属开阔眼界，不怎么实用。
2.  检查素数的正则表达式  [http://coolshell.cn/articles/2704.html][http_coolshell.cn_articles_2704.html]  数字n用  1111。。1 （n个1）表示，纯属坑爹。

[http_coolshell.cn_articles_3738.html]: http://coolshell.cn/articles/3738.html
[http_coolshell.cn_articles_2704.html]: http://coolshell.cn/articles/2704.html