脚本宝典收集整理的这篇文章主要介绍了【学习笔记】欧拉筛法(线性筛素数),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
算法介绍:欧拉筛法是在O(N)线性时间内实现素数筛选的优秀算法。
算法思路:总体上与Eratosthenes筛法类似,也是用较小的数筛去较大的合数。
结合代码分析:
inline void Euler_Sieve(){
for(register int i=2;i<=n;i++){
if(isPrime[i]) pri[++cnt]=i;
for(register int j=1;j<=cnt&&i*pri[j]<=n;j++){
isPrime[i*pri[j]]=false;
if(i%pri[j]==0) break;
}
}
}
对每一个数i,无论其是否为质数,都可以用其筛去其他数。
设1<=s<j<t
证明:若最小质因子比pri[j]小,则在循环到j之前就已break,不可能循环至pri[j]。
证明:引理1已证i的最小质因子为pri[j],故i*pri[j]最小质因子也应为pri[j]。引理2保证了被pri[j]筛掉的所有合数都满足线性条件。
证明方法如引理1。引理3保证了j之前所有被筛掉的合数都满足线性条件。
证明方法:由引理1可易证。故若j继续循环增大,则i*pri[t]将被pri[t]筛掉,但pri[t]并非其最小质因子,故不满足线性条件,故需break。
综上,当i%pri[j]==0的时候实行break操作可保证满足线性条件,实现线性筛。
以上是脚本宝典为你收集整理的【学习笔记】欧拉筛法(线性筛素数)全部内容,希望文章能够帮你解决【学习笔记】欧拉筛法(线性筛素数)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。