ACM 筛素数总结_acm训练总结

ACM 筛素数总结由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“acm训练总结”。

【总结】关于求素数的说【两种筛法】（学习小结，请无视）

素数大家都很熟了，不多说了，这里只想说一下求素数。

当然先是唯一素因子分解定理：合数a仅能以一种方式，写成如下的乘积形式：a=p1e1p2e2…prer 其中pi为素数，p1

对于一个整数n，当其在 小于sqrt（n）范围里有一个约数，那么必然在 大于sqrt（n)的范围里有对应的另一个Eratosthenes（埃拉托斯特尼筛法）都是到 sqrt（n）的范围。①。试除法判素数

对于大于1的正整数a，如果a具有小于或等于sqrt（a）的素因子，则a为合数，否则a为素数。

因此，可用区间[2,sqrt(a)]内的数去试除a，只要有一个数能整除a，则a为合数，否则a为素数。这种判断素复杂度O(sqrt(n)).IsPrime(a)for(i=2;i*i

return a为素数

②。Sieve Of Eratosthenes（埃拉托斯特尼筛法）可以筛出2~n 范围里的所有素数。

1)将所有候选数2~n放入筛中;2)找出筛中最小数P，P一定为素数。

3)宣布P为素数，并将P的所有倍数从筛中筛去;4)重复2)至3)直到筛空.其实，当P>sqrt(n)时筛中剩下的数就已经都是素数了。//用数组prime[MAXN]记录是否为素数； //prime[i]为0表示i为素数，否则为合数 int prime[MAXN]={0};for(i=2;i*i

对于Sieve Of Eratosthenes，普通的筛法如果是一个合数，那么会被多次筛掉，比如6,当2作为素数时筛掉一线性筛法保证所有合数只被筛掉一次

具体详见《ftfish利用积性函数的优化》，讲到了 积性函数（对于正整数n的一个算术函数f(n)，当中f(1)=1且称它为积性函数。）

for(int i = 2;i

for(int j = 0;j

fg[i*prim[j]] = 1;if(i % prim[j] == 0)break;//这一步保证了筛法是线性的，这是整个算法的关键

} } 摘：

利用了每个合数必有一个最小素因子。

每个合数仅被它的最小素因子筛去正好一次。所以为线性时间。代码中体现在：

if(i%prime[j]==0)break;prime数组 中的素数是递增的,当 i 能整除 prime[j]，那么 i*prime[j+1] 这个合数肯定被 prime[j] 乘以某个数筛因为i中含有prime[j], prime[j] 比 prime[j+1] 小。接下去的素数同理。所以不用筛下去了。在满足i%pr[j]==0这个条件之前以及第一次满足改条件时,pr[j]必定是pr[j]*i的最小因子。