我遇到了埃拉托色尼筛的分段实现，它的运行速度比传统版本快很多倍。
有人可以解释一下分段如何提高运行时间吗？
请注意，我想在其中找到素数[1,b].
它适用于这个想法：（用于查找 10^9 之前的质数）
-
我们首先生成 sqrt(10^9) 以下的筛选素数，这是交叉倍数所需的。然后我们开始交叉第一个素数2的倍数，直到达到2>=segment_size的倍数，如果发生这种情况，我们使用(multiple-segment_size)计算下一个段中该倍数的索引并将其存储在单独的数组（下一个[]）。然后，我们使用相同的过程交叉掉下一个筛选素数的倍数。一旦我们划掉了第一段中所有筛选素数的倍数，我们就迭代筛选数组并打印出（或计算）素数。
-
为了筛选下一个段，我们重置筛选数组，并将较低的偏移量增加segment_size。然后我们再次开始交叉倍数，对于每个筛分素数，我们从下一个数组中检索筛子索引，然后从那里开始交叉倍数......
分段筛执行与常规筛相同的所有操作，因此 big-O 时间复杂度保持不变。区别在于内存的使用。如果筛子足够小以适合内存，则没有区别。随着筛子尺寸的增加，参考局部性成为一个因素，因此筛分过程减慢。在极端情况下，如果筛子不适合内存并且必须分页到磁盘，则筛分过程将变得非常慢。分段筛子保持内存大小恒定，并且可能很小，因此筛子的所有访问都是本地的，因此速度很快。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
