阿特金超大素数筛的素数硬盘存储

Question

我已经实现了Sieve of Atkin，它在接近100000000的素数下工作得很好。除此之外，它会因为记忆问题而崩溃。在

在算法中，我想用基于硬盘驱动器的数组替换基于内存的数组。Python的“wb”文件函数和Seek函数可以做到这一点。在我开始发明新轮子之前，有人能给我些建议吗？一开始就出现了两个问题：

1. 有没有一种方法可以“大块”Atkin的筛子来处理内存中的段
2. 有没有一种方法可以挂起活动，然后再回来——建议我可以序列化内存变量并恢复它们。

我为什么要这么做？一个老古董，想找点乐子，让面条继续工作。在

Answer 1

首先，您应该确保以高效的方式存储数据。通过使用位图，您可以轻松地将多达100000000个素数的数据存储在12.5Mb内存中，通过跳过明显的非素数（偶数等），您可以使表示更加紧凑。这也有助于在硬盘上存储数据。当你在100000000个素数时遇到麻烦，说明你没有有效地存储数据。在

如果你没有得到更好的答案，有些提示。在

1.Is there a way to "chunk" the Sieve of Atkin to work on segment in memory

是的，对于类似eratothenes的部分，您可以做的是在“parallel”（一次一个块）中运行筛选列表中的多个元素，这样就可以最大限度地减少磁盘访问。在

第一部分比较棘手，您需要做的是以更有序的顺序处理4*x**2+y**2、3*x**2+y**2和{}。一种方法是先计算它们，然后对数字进行排序，有一些排序算法在驱动器存储（仍然是O（N logn））上运行良好，但这会降低时间复杂性。一个更好的方法是迭代x和{}，因为一个块是由一个间隔决定的，你可以简单地迭代所有x和{}，这样{}。在

2.is there a way to suspend the activity and come back to it later - suggesting I could serialize the memory variables and restore them

为了实现这一点（无论程序以何种方式和何时终止），您必须首先对磁盘进行日志记录访问（fx使用SQL数据库保存数据，但您可以谨慎地自己执行）。在

第二，由于第一部分中的操作不是独立的，所以必须确保不要重复这些操作。然而，由于您将运行的部分块一个块，您可以简单地检测哪个块是最后一个处理的块，并在那里继续（如果您可以结束部分处理的块，您只需丢弃它并重新执行该块）。对于Erastothenes部分，它是独立的，所以你可以运行所有它，但是为了提高速度，你可以在筛选完它们之后存储一个生成的素数列表（这样你可以在最后一个生成的素数之后继续进行筛选）。在

作为一个副产品，你甚至应该能够以一种方式构造程序，使得即使在第二步运行的情况下也能保留第一步中的数据，从而在以后通过继续第一步，然后再次运行第二步来扩展限制。甚至可能有两个程序，当你厌倦了第一个程序，然后把它的输出输入到Eratosthenes部分（因此不必定义限制）。在