如何优化eratosthenes的筛子以便存储非常大范围的素数？

Question

我已经研究了Eratosthenes的Sieve的工作,使用迭代生成到达给定数字的素数并且去掉所有复合数.并且算法只需要迭代到sqrt(n),其中n是我们需要找到所有素数的上限. 我们知道,与复合数的数量相比,最多n = 10 ^ 9的素数的数量非常少.因此,我们使用所有空间来通过标记它们的复合来告诉这些数字不是首要的.我的问题是我们可以修改算法只是存储素数,因为我们处理的范围非常大(因为素数的数量非常少)？我们可以直接存储素数吗？

Answer 1

将结构从一组(筛子) - 每个候选者一位 - 更改为存储质数(例如,在列表,向量或树结构中)实际上增加了存储要求.

示例:在2 ^ 32以下有203.280.221个素数.uint32_t该大小的阵列需要大约775 MiB,而相应的位图(也称为集合表示)仅占用512 MiB(2 ^ 32位/ 8位/字节= 2 ^ 29字节).

具有固定单元大小的最紧凑的基于数字的表示将存储连续奇数素数之间的减半距离,因为最多约2 ^ 40,所以减半的距离适合于一个字节.对于素数高达2 ^ 32的193 MiB,这比仅有几率的位图略小,但它仅对顺序处理有效.对于筛分它不适合,因为正如Anatolijs指出的那样,像Eratosthenes筛子这样的算法实际上需要一组表示.

通过省略多个小素数,可以大大缩小位图.最着名的是仅有赔率的表示,它排除了数字2及其倍数; 这将空间需求减少到256 MiB,几乎不增加代码复杂性.您只需要记住在需要时从空气中拉出数字2,因为它没有在筛子中显示.

通过省去多个较小的素数,可以节省更多的空间; 这种"仅限赔率"技巧的概括通常被称为"轮式存储"(参见维基百科中的车轮分解).然而,向车轮添加更多小质数的增益越来越小,而车轮模数("周长")则爆炸性地增加.添加3删除剩余数字的1/3,添加5除去另外的1/5,添加7只能再获得1/7,依此类推.

这里是一个概述,为车轮增加另一个素数可以得到什么.'ratio'是相对于代表每个数字的全套轮式/减少组的大小; 'delta'给出与前一步骤相比的收缩."辐条"是指需要表示/存储的含铅辐条的数量; 车轮的辐条总数当然等于其模数(周长).

mod 30车轮(大约136 MiB,质量高达2 ^ 32)提供了极佳的成本/效益比,因为它有八个主轴承轮辐,这意味着车轮和8-之间存在一对一的对应关系.位字节.这可以实现许多有效的实现技巧.然而,尽管存在这种偶然的情况,其增加的代码复杂性的成本是相当大的,并且出于许多目的,仅有几率的筛子('mod 2 wheel')给予了最大的降价.

还有两个值得记住的额外考虑因素.首先,像这样的数据大小通常会大大超过内存缓存的容量,因此程序通常会花费大量时间等待内存系统传递数据.筛选的典型访问模式使这种情况更加复杂 - 一次又一次地跨越整个范围.通过以适合处理器的1级数据高速缓存的小批量处理数据(通常为32 KiB),可以实现几个数量级的加速; 通过保持L2和L3高速缓存的容量(分别为几百KiB和几个MiB),仍然可以实现较低的加速.这里的关键字是"分段筛分".

第二个考虑因素是许多筛分任务 - 如着名的SPOJ PRIME1及其更新版本PRINT(具有扩展范围和收紧的时间限制) - 仅需要在上限的平方根上的小因子素数永久可用于直接访问.这是一个相对较小的数字:在PRINT的情况下筛分高达2 ^ 31时为3512.

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