python - 用于超大素数的素数硬盘存储 - 阿特金筛法

Question

我已经实现了 Sieve of Atkin它适用于接近 100,000,000 左右的质数。除此之外，它还会因为内存问题而崩溃。

在算法中，我想用基于硬盘的阵列替换基于内存的阵列。 Python 的“wb”文件函数和 Seek 函数可以解决问题。在我开始发明新轮子之前，有人可以提供建议吗？一开始就出现了两个问题:

1. 有没有办法将阿特金筛法“分 block ”以处理内存中的片段，以及
2. 有没有办法暂停事件并稍后返回 - 建议我可以序列化内存变量并恢复它们。

我为什么要这样做？一个寻找娱乐并保持面条工作的老头。

Answer 1

用 Python 实现 SoA 听起来很有趣，但请注意，在实践中它可能比 SoE 慢。对于一些好的单片 SoE 实现，请参阅 RWH's StackOverflow post .这些可以让您了解非常基本的实现的速度和内存使用情况。 numpy 版本将在我的笔记本电脑上筛选超过 10,000M。

您真正想要的是分段筛子。这使您可以将内存使用限制在某个合理的限制范围内(例如 1M + O(sqrt(n))，如果需要可以减少后者)。 primesieve.org 中显示了一个很好的 C++ 讨论和代码。 .您可以在 Python 中找到各种其他示例。 primegen ，Bernstein 的 SoA 实现是作为分段筛实现的(您的问题 1:是的，SoA 可以分段)。这与筛选范围密切相关(但不完全相同)。这就是我们如何使用筛子在几分之一秒内找到 10^18 和 10^18+1e6 之间的素数——我们当然不会将所有数字筛到 10^18+1e6。

在我看来，涉及硬盘是错误的方向。我们应该能够比从驱动器中读取值更快地进行筛选(至少使用良好的 C 实现)。范围和/或分段的筛子应该可以满足您的需要。

有更好的存储方式，这会对一些人有所帮助。我的 SoE 和其他几个一样，使用 mod-30 轮子，因此每 30 个整数有 8 个候选，因此每 30 个值使用一个字节。看起来 Bernstein 的 SoA 做了类似的事情，每 60 个值使用 2 个字节。 RWH 的 python 实现不完全存在，但足够接近每 30 个值 10 位。不幸的是，Python 的 native bool 数组似乎每位使用大约 10 个字节，而 numpy 是每位一个字节。要么使用分段筛，不要太担心它，要么找到一种在 Python 存储中更高效的方法。