c++入门必学算法 质数筛

一、什么是质数筛

质数筛也叫素数筛，是求1到n之内素数的优化算法，质数筛有两种，埃氏筛和欧拉筛。

埃氏筛的时间复杂度接近O(n*logn)，而欧拉筛可以把复杂度降低到O(n)，下面看两种算法的到底是如何一步步优化的吧

二、暴力枚举

暴力法求解复杂度O(n)*$\sqrt{n}$，是新手必学的算法，能解决小数据的素数判断

1、暴力枚举基本思想：

从1到n枚举每一个数，判断每个数是不是素数。质数的定义就是只能被1和自身整除的数字，例如2、3、5、7、11、13…等等，对于每一个数，我们只需要判断这个定义即可

2、模板代码

#include
#include//需要用到sqrt()函数 
using namespace std;

//判断素数
bool prime(int val){
//     1-3的值需要特判，因为我们循环判断只判断到sqrt(val)，1-3是判断不了的
    if(val==1)return 0;
    if(val==2||val==3)return 1;
//     为什么只要判断到sqrt(val)？
//     例如一个数8，它的因数有1、2、4、8，可以发现1<2
//     所以我们只要判断小于sqrt(8)的数就可以了,因为因数都是成对出现的
    for(int i=2;i<=sqrt(val);i++){
//         如果被整除了,那么该数一定不是素数,返回0
        if(val%i==0)return 0;
    }
//     如果是素数就返回1
    return 1;
}

int main(){
    int n;
    cin>>n;
    for(int i=2;i<=n;i++){
//         如果返回值是1,那么该数是素数,输出即可
        if(prime(i)==1){
            cout<<i<<' ';
        }
    }
}

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
31

3、运行结果

输入：
100
输出：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
1
2
3
4

三、埃氏筛

埃氏筛复杂度接近O(n)*$\log n$，是比较容易理解、容易学习的算法

1、埃氏筛基本思想：

如果一个数是素数，那么它的倍数就不是素数。

例如：
2是素数，那么4、6、8、10、12…都不是素数

3是素数，那么6、9、12、15、18…都不是素数

4不是素数，在2的时候已经知道4不是素数了，我们不必重复说明8、12、16…等等不是素数，因为这些数在2的时候已经可以证明它们不是素数了

5没有被2、3、4标记为它不是素数，那么就说明5不能被2、3、4整除，哪么就说明5是素数

6被在3的时候被标记为不是素数了，直接跳过

7和5一样，没有被2、3、4、5、6标记为不是素数，那么7就是素数，而14、21、28…都不是素数

…

以上就是埃氏筛的基本思想，我们模拟上面的过程即可快速求出1到n所有的素数

2、模板代码

#include
using namespace std;
int main(){
//	  f[i]=1代表i不是素数，f[i]=0代表i是素数 
	int f[100010]={1,1};
    int n;
    cin>>n;
//    埃氏筛 
    for(int i=2;i<=n;i++){
    	if(f[i]==1)continue;
    	for(int j=2;i*j<=n;j++){
    		f[i*j]=1;
		}
    }
//    打印 
    for(int i=0;i<=n;i++){
    	if(f[i]==0){
    		cout<<i<<' ';
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3、运行结果

输入：
100
输出：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
1
2
3
4

四、欧拉筛

欧拉筛又叫线性筛，可以把问题时间复杂度优化到O(n)。是求范围内素数最好用的算法

1、对比埃氏筛

埃氏筛的复杂度为什么达不到O(n)呢？因为它在标记不是素数的时候存在大量的重复操作。

例如：
12，它在2、3的时候都被标记了1次
30，它在2、3、5的时候都被标记了1次

欧拉筛的巧妙之处在于它能去掉重复的标记

2、欧拉筛的基本思想

保证每个数只被除1以外最小的质因数标记

例如：
12，它有质因数2、3，那么它只被2标记
15，它有质因数3、5，那么它只被3标记
30，它有质因数2、3、5，那么它只被2标记

实现：
(1) 需要用一个数组 p[n] 把找到的素数存下来

(2) 我们需要逆向思考，从最大的因数找到最小的质因数，例如12，我们通过6，找到质因子2，即当我们处理6的时候需要把12给标记为不是素数

(3)处理一个数时我们遍历每一个已经有的质数，当该质数是该数的因数是退出，因为对于后面的数来说，该数不是最大的因数了！这一步是有点难理解的，慢慢来，多推敲几遍

第三点理解：
例如当前的数是9，那么此时已经找出了质数2、3、5、7
遍历这些质数，那么9*2=18不是质数，9*3=27不是质数，9*5=45不是质数，9*7=63也不是质数，但实际上我们在更新完 27 之后就应该退出了，而不去更新45和63。

因为9并不是45的最大因数，15才是，即这个数在处理15的时候会被标记的，如果现在标记就会出现无用的标记了。

63也是一样的道理，它的最大因数是21，即这个数在处理21的时候会被标记。

为什么处理9的时候，3之后的5、7，最大的因数都不是9？而3和3之前最大因数都是9呢？

我们可以把3当作桥梁，因为3是9的因数，遍历5、7时，9*5可拆分为3*3*5=3*15，9*7可拆分为3*3*7=3*21，而2、3都是不可分的，2*9、3*9，最大的因数就是9，它们的数值应该在此时更新为不是素数

3、模板代码

#include
using namespace std;
int main(){
	int d=0;
	int p[100010]={0};
	int f[100010]={1,1};
	int n;
	cin>>n;
	for(int i=2;i<=n;i++){
		if(f[i]==0){//如果没被标记过，那么i是质数 
			p[d++]=i;
		}
		for(int j=0;j<d;j++){
			if(p[j]*i<=n){//标记以i为最大因数的数为不是素数（除了1和本身） 
				f[p[j]*i]=1;
			}else{
				break;
			}
			if(i%p[j]==0){//如果p[j]是i的因数，那么后面的数都不是以i为最大因数的 
				break;
			}
		}
	}
	
	for(int i=0;i<d;i++){//打印1到n的质数 
		cout<<p[i]<<' ';
	}
	
} 

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

3、运行结果

输入：
100
输出：
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
1
2
3
4

五、总结

埃氏筛的实现原理是比较简单的，使用的场景也比较广泛，但在个别的竞赛题中会卡这点时间，必须使用欧拉筛。

欧拉筛理解的过程是有点难的，但在真正理解之后思路会非常清晰，看不懂就多看两遍

加油咯！兄弟萌