筛法学习笔记

唯一分解定理：对于一个大于1的自然数N，如果N是合数，那么N可以唯一分解为有限个质数的乘积
在判断一个数n是否为质数时，首先想到的是取i遍历2到x/2找是否存在i为n的因子，若没找到则n为质数。这样进行了约n/2次计算。
若要找出1到n中所有的质数时，用上述方法显然效率低下，这时可以使用筛质数法。
质数的定义是：除了1和本身之外，不存在其他因子的大于1的自然数。一个质数的倍数必然是合数，故可以通过将一个质数的倍数筛除的做法来保留质数，又因为唯一分解定理，当我们从最小的质数2开始，筛除所有2的倍数，则留下来的数包括其他质数 以及 以其他质数为因子的合数，那么以其他质数为因子的合数必然大于其他质数，故下一个没被筛除的最小的数一定是一个质数。

埃氏筛

埃氏筛就是从最小的质数2开始，将没被筛除的数认定是质数，然后筛除它的所有倍数。

int prime[N];	// prime[i] 为0则 i为质数，为1则i为合数
void get_prime(int n){
prime[0] = prime[1] = 1;
//0 和 1 不是质数
for(int i = 2; i <= n; i ++){
if( !prime[i] )
for( int j = i + i; j <= n; j += i) prime[j] = 1;
}
}

埃氏筛的复杂度为O(nlognlogn)
可以发现，埃氏筛存在一个问题，即一个合数被筛了多次，譬如6的因子既包含了质数2，又包含了质数3，那么当i = 2时6会被筛除一次，i = 3 时6又会被再筛除一次。

欧拉线性筛

欧拉筛在埃氏筛的基础上优化为每个数只会筛除1次，达到了线性的时间复杂度O(n)。

bool visit[N];
//visit标记合数
int prime[N], cnt;
//prime存所有质数
void get_prime(int n){
for(int i = 2; i <= n; i ++){
if( !visit[i] ) prime[cnt++] = i;
for( int j = 0 ; prime[j] <= n/i ; j ++ ){
visit[prime[j] * i] = 1;
//标记质数的i倍的合数
if(i % prime[j] == 0) break;
//线性优化关键
}
}
}

自己手动模拟一下n=6的过程加深理解，因为唯一分解定理，所以当 i % prime[j] == 0 ，即prime[j]是i的因子的时候，就没必要去筛i * prime[j + 1]了，因为i可以写为prime[j] * k，prime[j+1] * i必然等价于 prime[j] * kprime[j + 1] ，所以当i循环至i = kprime[j+1]时自然会筛掉之前没筛的合数，做到每个数只筛选1次。

最后

以上就是潇洒咖啡豆为你收集整理的质数筛法学习笔记筛法学习笔记的全部内容，希望文章能够帮你解决质数筛法学习笔记筛法学习笔记所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。