分割如何改善Eratosthenes筛选的运行时间?

我遇到了一个分段的Eratosthenes筛子实施,它的运行速度比传统版本高出许多倍。 有人可以解释一下细分如何改善运行时间? 请注意,我想在[1,b]中找到素数。

它适用于这个想法:(寻找素数到10 ^ 9)

  • 我们首先生成低于sqrt(10 ^ 9)的筛分质数,这是交叉多次所需的。 然后我们开始交叉第一个素数2的倍数,直到我们达到2> = segment_size的倍数,如果发生这种情况,我们使用(multiple – segment_size)计算下一个段中该倍数的索引并将其存储在一个单独的array(next [])。 然后我们使用相同的程序交叉下一个筛分素数的倍数。 一旦我们在第一段中划掉所有筛分质数的倍数,我们就在筛子arrays上迭代并打印出(或计数)质数。

  • 为了筛选下一个段,我们重置了筛子arrays,并通过segment_size增加了较低的偏移量。 然后我们再次开始交叉倍数,对于每个筛选素数,我们从下一个数组中检索筛子索引,然后我们从那里开始交叉倍数…

分段筛的操作与常规筛相同,因此大O时间复杂度不变。 不同之处在于使用内存。 如果筛子足够小以适合记忆,则没有区别。 随着筛子尺寸的增加,参考局部成为一个因素,因此筛分过程减慢。 在极端情况下,如果筛网不适合存储器并且必须被分页到磁盘,则筛分过程将变得非常慢。 分段筛使记忆大小保持恒定,并且可能很小,因此筛的所有访问都是局部的,因此很快。

即使筛子完全适合RAM,访问的位置仍然会产生很大的不同。 仅有几率的Eratosthenes的C ++实现需要将近半分钟来筛选前2 ^ 32个数字; 相同的实现初始化相同的筛子在256 KB的小片段(2 ^ 21位,代表2 ^ 22个数字)在我老化的Nehalem上只需8.5秒,其256 KB的L2缓存。

由于筛网必须每次迭代所有因子直至sqrt(n),所以筛选在小缓存友好区段中的筛选速度减小,因为筛网必须迭代所有因子,无论该区段有多小或多大。 这对于接近2 ^ 64的区段最为显着,其中小因子包括203,280,221个素数(即完整的32位筛)。

不过,分段操作仍然可以完全筛分。 您可以将接近2 ^ 64的段扫描到每秒数百万个质数,在较低区域每秒数千万。 这是计算素数,而不是原始数量矿石。 即使你有大量的记忆,全筛也不会超过2 ^ 32左右。