分割如何提高Eratosthenes筛的运行时间？

Question

我遇到了Eratosthenes筛的分段实现，它承诺运行速度比传统版本快很多倍。 有人可以解释如何细分改善运行时间？ 请注意，我想查找[1，b]中的素数。

它适用于这样的观念：（寻找素数，直到10^9）

• 我们首先生成这是需要跨断倍数低于开方筛分素数（10^9） 。然后我们开始交叉第一个素数2的倍数，直到我们达到2> = segment_size的倍数，如果发生这种情况，我们使用（multiple-segment_size）计算下一个分段中该倍数的索引并将其存储在单独的数组（下一个[]）。然后，我们使用相同的程序将下一个筛选素数的倍数分离。一旦我们将第一个区段中所有筛分素数的倍数交叉，我们遍历筛选数组并打印（或计数）素数。

• 为了筛选下一个段，我们重置筛数组，并且通过segment_size递增较低的偏移量。然后我们再次启动渡客的倍数，每个筛分总理，我们从下一个数组检索筛指标，我们开始穿越过倍数从那里...

Answer 1

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

Answer 2

即使筛子完全适合RAM，访问的地点仍然有很大的差异。一个C++实现的赔率只Eratosthenes需要几乎半分钟筛选前2^32的数字;在我的老化Nehalem中，256K字节的二级缓存只需要8.5秒就可以完成同样的初始化小256K字节段（2^21位，代表2^22个数）的筛选。

从小型高速缓存友好段中筛选的加速在该范围的较高区域中减少，因为筛选必须每次迭代所有高达sqrt（n）的因子，而不管其大小段是。对于接近2^64的片段，其中小因素包括203,280,221个素数（即完整的32位筛）最为显着。尽管如此，分段操作仍然能够完全完成筛分。您可以筛选接近2^64的片段，以达到每秒数百万个素数的调整，在较低的区域每秒数千万。这是在计算素数，而不是原始数量的矿石。即使你拥有大量的记忆，全筛仍然不能超过2^32左右。