我使用"埃拉托色尼筛子"来产生素数。
def primes(n):
if n < 2:
return None
primes_sieve = [True] * (n + 1)
primes_sieve[1] = False
primes_sieve[0] = False
# sieve
for i in range(2, int(n ** 0.5) + 1):
if primes_sieve[i]:
for j in range(i * i, n + 1, i):
primes_sieve[j] = False
return [i for i, p in enumerate(primes_sieve) if p]
它适用于少量。
In [28]: primes(2**10)[:10]
Out[28]: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
In [29]: primes(2**10)[-10:]
Out[29]: [967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021]
In [30]: primes(2**15)[-10:]
Out[30]: [32633, 32647, 32653, 32687, 32693, 32707, 32713, 32717, 32719, 32749]
对于一些大数字，它会任意报告错误。
内存错误
In [32]: primes(2**30)[-10:]
---------------------------------------------------------------------------
MemoryError Traceback (most recent call last)
<ipython-input-32-3e546166a3d9> in <module>
----> 1 primes(2**30)[-10:]
<ipython-input-26-5f07bf9cb49e> in primes(n)
2 if n < 2:
3 return None
----> 4 primes_sieve = [True] * (n + 1)
5 primes_sieve[1] = False
6 primes_sieve[0] = False
MemoryError:
和溢出错误：
In [35]: primes(2**100)[-10:]
---------------------------------------------------------------------------
OverflowError Traceback (most recent call last)
<ipython-input-35-3bb8857d5f28> in <module>
----> 1 primes(2**100)[-10:]
<ipython-input-26-5f07bf9cb49e> in primes(n)
2 if n < 2:
3 return None
----> 4 primes_sieve = [True] * (n + 1)
5 primes_sieve[1] = False
6 primes_sieve[0] = False
OverflowError: cannot fit 'int' into an index-sized integer
怎么了？我很高兴也很好奇地发现python也有OverflowError。
Pythonlist被实现为指向 Python 对象的指针的动态大小的 C 数组。当您执行以下操作时：
primes_sieve = [True] * (n + 1)
其中n2**30，您要求2**32(在 32 位系统上(或2**33(在 64 位系统上(字节的单个连续内存分配。在 Python 的 32 位构建上，前者是不可能的;整个虚拟内存地址空间 user + 内核为2**32字节，其中一些不可用，其中一些已经在使用中。Python 会立即拒绝请求比地址空间更多的内存。即使在 64 位系统上，系统也可能出于任何原因拒绝对这么多内存的请求(例如，如果页面文件/交换文件中没有足够的空间来处理该内存(，Python 将以相同的方式报告它，作为MemoryError。
OverflowError只是告诉您，您传递的值无法适应所涉及的基础 C 类型。list(在CPython上(将其大小存储为signed size_t(Py_ssize_t是typedef(，仅限于2**31 - 1或2**63 - 1;无论哪种方式，都比2 ** 100 + 1小得多.在CPython尝试执行分配之前，它正在尝试提取请求的大小作为signed size_t，并在无法这样做时立即死亡。
关键是，试图制造list的大小2**30几乎总是错误的，而制造一个大小2**100(不能适应世界上任何系统(从一开始就注定要失败。你不能让埃拉托色尼的筛子用Python或任何其他语言进行完整的筛子2**100;充其量，你可以将零碎的东西筛到大约2**64(通过筛选范围顶部的平方根，然后使用这些数字来筛选一小部分数字，就像你似乎正在测试的前 10 个，但不是整个范围(。
旁注：如果你正在实现一个埃拉托色尼筛，减少内存消耗的第一步是替换：
primes_sieve = [True] * (n + 1)
跟：
primes_sieve = bytearray('x01') * (n + 1)
这将减少筛子中每个项目的成本，从指针到单个字节，将内存使用量减少 4-8 倍。您可以通过仅存储奇数上的信息来进一步将内存需求减半(因为除了可以硬编码的2之外，只有奇数可以是素数(。从那里，您可以转向使用可以提供打包位集的第三方类(将内存使用量再减少 8 倍，从字节减少到位(。有进一步的优化可用，但其中大多数在 Python 中会很慢(你必须移动到 C 才能看到好处(;这可以是你的研究。