如何优化eratosthenes的sieve来存储很大范围内的质数？

Question

我研究了埃拉托斯特尼筛的工作，通过迭代和删除所有合成数，生成素数到给定数。算法只需要迭代到sqrt（n），其中n是上界，我们需要找到所有素数。我们知道，与复合数的数量相比，n=10^9之前的素数的数量非常少。所以我们用所有的空间来表示这些数字不是质数，首先将它们标记为复合数。我的问题是，由于我们处理的范围非常大（因为素数非常少），我们可以修改算法来只存储素数吗？我们能直接存储素数吗？

Answer 1

一旦您证明每个复合数是复合的，您就可以从数组/矢量中删除它。或者，当您填写一组数字以通过筛子时，删除所有偶数（2除外）和所有以5结尾的数字。

Answer 2

你可以这样做(从你的数组/链表中删除被检测为非素数的数字)，但这样算法的时间复杂度会退化到O(N^2/log(N))之类的，而不是原来的O(N*log(N))。这是因为你不能说“数字2X，3X，4X，...”不再是质数了。你将不得不遍历整个压缩列表。

Answer 3

将结构从集合(筛)-每个候选者一位-改变为存储素数(例如，在列表、向量或树结构中)实际上增加了存储需求。

例如：在2^32以下有203.280.221个素数。该大小的uint32_t数组需要大约775 MiB，而相应的位图（也称为集合表示）仅占用512 MiB（2^32位/8位/字节=2^29字节）。

具有固定单元大小的最紧凑的基于数字的表示将存储连续奇素数之间的减半距离，因为直到大约2^40，该减半距离适合一个字节。对于193 MiB的素数，直到2^32，这比odds-only位图稍小，但它仅对顺序处理有效。对于筛选来说，这是不合适的，因为正如Anatolijs所指出的，像厄拉多塞筛这样的算法实际上需要一个集合表示。

通过去掉小素数的倍数，位图可以大幅缩小。最著名的是排除了数字2及其倍数的奇数表示法；这将空间需求减半至256 MiB，而几乎没有增加代码复杂性的成本。你只需要记得在需要的时候从稀薄的空气中拉出数字2，因为它不在筛子中出现。

省去更多小素数的倍数可以节省更多空间；这种“仅概率”技巧的泛化通常被称为“轮式存储”（参见维基百科中的轮式分解）。然而，向车轮添加更多的小底漆所获得的收益越来越小，而车轮模量（“环境”）则呈爆炸性增长。加3会去掉剩余数字的1/3，加5会再去掉1/5，加7只会再得到1/7，依此类推。

这里有一个概述，增加另一个质数能给你带来什么。“比率”是相对于代表每个数字的完整集合的轮式/简化集合的大小；“delta”给出了与上一步相比的收缩率。“辐条”是指需要表示/存储的主轴承辐条的数量；一个轮子的辐条总数当然等于它的模数(周长)。

mod 30车轮（对于高达2 ^ 32的素数，约为136 MiB）提供了出色的成本/效益比，因为它具有八个主要轴承辐条，这意味着车轮和8位字节之间存在一对一的对应关系。这实现了许多有效的实施技巧。然而，尽管这种情况很偶然，但它在增加代码复杂性方面的成本相当可观，并且出于许多目的，仅赔率筛（“mod 2轮”）到目前为止给出了最大的收益。

还有两个额外的注意事项值得记住。第一，像这样的数据大小通常会大大超过内存缓存的容量，因此程序通常会花费大量时间等待内存系统传递数据。这与典型的筛选访问模式更加复杂——一次又一次地跨越整个范围。通过将数据小批量处理到处理器的1级数据高速缓存（通常为32 KiB）中，可以实现几个数量级的加速；通过保持在L2和L3缓存（分别为几百KiB和几个MiB）的容量范围内，仍然可以实现较小的加速。这里的关键词是“分段筛选”。

第二个考虑因素是，许多筛分任务 - 如著名的SPOJ PRIME1及其更新版本PRINT（具有扩展的边界和更严格的时间限制） - 只需要小因子素数到上限的平方根才能永久用于直接访问。这是一个相对较小的数字：3512，当筛分到2 ^ 31时，就像PRINT的情况一样。

由于这些素数已经过筛分，因此不再需要集合表示，并且由于它们很少，因此存储空间没有问题。这意味着它们最有利可图地保留在向量或列表中作为实际数字，以便于迭代，可能带有额外的辅助数据，如当前工作偏移量和相位。然后，通过称为“窗口筛分”的技术轻松完成实际的筛分任务。在PRIME1和PRINT的情况下，这比将整个范围筛分到上限快几个数量级，因为这两个任务都只需要筛分少量子范围。