关于如何理解欧拉筛

/ 0评 / 0

如果你习惯用埃氏筛,那么在试图理解欧拉筛的时候可能碰上一些墙壁。我在网上没有找到特别好的快速解释,这里就写一下权当记录了。

你需要理解欧拉筛在做什么,以及为什么比埃氏筛快。

埃氏筛的本质,是用一个游标从小到大遍历数字,遇到一个没有被标记过的数字,就将其标记为质数,并接下来启动另一个游标,新的游标将继续向后移动,将所有这个质数的倍数标记为合数

埃氏筛不够快的原因在于,一个合数的质因数可能不止一个,这就意味着一个合数可能被好几个质数重复筛选好几次。例如6=2*3,那么6会被2筛,也会被3筛,这里的重复就造成了时间性能的下降。

而欧拉筛则保证了一个合数只会被筛选一次,代价是一个辅助空间用以归类质数。

下面是欧拉筛的原理:

欧拉筛使用一个参考倍数+质数表完成筛选(如果你错误地认为也是两个指向目标数字的游标,那你可能很难理解)。 这里将倍数记作 i,将质数表记作prime[ ],它的游标记作 j ,一个vitst数组记作vis[ ]。

从2开始枚举倍数 i,对于每一个 i,用 j 从小到大遍历质数表中的元素。将要被检查的元素不是 i,也不是 j,而是 i*prime[ j ]。如果 i*prime[ j ]从来没有被访问过,则这个数字(i*prime[ j ])是质数,将之追加到质数表prime[ ]中。

这里有一个特殊判断,就是当参考倍数 i 恰好是质数表中的元素prime[ j ]的倍数时,立即停止枚举 j,转而枚举新的 i。原因很简单,这里要强调筛选目标是 i*prime[ j ],如果 i 是某个质数的倍数,那么后续所有的筛选目标i*prime[ j+k ]不但会是prime[ j+k ]的倍数,还会是prime[ j ]的倍数。

然而欧拉筛的目标是每个数字只被筛一次,因此规定了筛选目标 i*prime[ j ] 的最小质因数是 prime[ j ]。如果继续向后筛,则筛选目标的最小质因数将始终为 prime[ j ],这将违反欧拉筛的筛选原则,所以需要使用一个特殊判断结束这个小循环。

以上。

发表评论

电子邮件地址不会被公开。 必填项已用*标注