如果数组中的数字太多，素数生成器会因内存错误而崩溃

Question

我有一个质数生成器，我很想知道我可以得到一个基于优化的质数生成器有多小和多快：

from math import sqrt
def p(n):  
  if n < 2: return []  
  s = [True]*(((n/2)-1+n%2)+1)  
  for i in range(int(sqrt(n)) >> 1):  
    if not s[i]: continue  
    for j in range( (i**i+(3*i) << 1) + 3, ((n/2)-1+n%2), (i<<1)+3): s[j] = False   
    q = [2]; q.extend([(i<<1) + 3 for i in range(((n/2)-1+n%2)) if s[i]]); return len(q), q  
print p(input())

生成器效果很好！速度超快，欢迎尝试。但是，如果您输入的数字大于 10^9 或 10^10（我认为），它将因内存错误而崩溃。我不知道如何扩展它使用的内存，以便它可以根据需要使用。任何建议将不胜感激！

我的问题与this一个非常相似，但这是Python，而不是C。

编辑：这是我尝试运行 10^9.

时得到的与内存相关的回溯之一

python prime.py
1000000000
Traceback (most recent call last):
  File "prime.py", line 9, in <module>
    print p(input())
  File "prime.py", line 7, in p
    for j in range( (i**i+(3*i) << 1) + 3, ((n/2)-1+n%2), (i<<1)+3): s[j] = False
MemoryError

Answer 1

问题在第 7 行。

for j in range( (i**i+(3*i) << 1) + 3, ((n/2)-1+n%2), (i<<1)+3): s[j] = False

特别是这部分：i**i

1000000000^1000000000 是一个 9 * 10^9 长的数字。如果不是 Tb，存储它需要多个 Gb（WolframAlpha 无法再计算它）。我知道 i 是 n 的平方根（最大），但在那么大的数字下差别不大。

如果可能，您必须将此计算分成更小的部分，并将其安全地保存在硬盘驱动器上。这使过程变慢，但可行。

Answer 2

首先，有一个问题，因为生成器说像 33、35 和 45 这样的数字是质数。

除此之外，这里还有几个结构占用内存：

s = [True]*(((n/2)-1+n%2)+1)

列表元素每个元素占用几个字节。对于 n = 10 亿，s 数组消耗了千兆字节。

range(...) 创建一个列表，然后遍历元素。尽可能使用 xrange(...)。

将 range() 转换为 xrange() 存在缺陷 - 例如看到这个 SO 答案：

OverflowError Python int too large to convert to C long

s 的更好实现是使用 Python 整数作为位数组，其密度为每字节 8 个元素。这是使用列表和整数之间的转换：

 s = [True]*(((n/2)-1+n%2)+1)        t = (1 << (n/2)+1)-1

 s[i]                                (t & (1<<i))
 not s[i]                            not (t & (1<<i))

 s[j] = False                        m = 1<<j
                                     if (t & m): t ^= m

更新

这是一个使用 yield 和 xrange 的未优化版本。对于较大的 n 值，请注意上述 xrange 的限制。

def primes(n):
  if n < 2: return
  yield 2
  end = int( sqrt(n) )
  t = (1 << n) -1

  for p in xrange(3, end, 2):
    if not (t & (1 << p)): continue
    yield p
    for q in xrange(p*p, n, p):
      m = t & (1<<q)
      if (t&m): t ^= m
      continue

  for p in xrange(end - (end%2) +1, n, 2):
    if not (t & (1 << p)): continue
    yield p


def test(n):
  for p in primes(n): print p

test(100000)

如果数组中的数字太多，素数生成器会因内存错误而崩溃

Prime number generator crashes from memory error if there are too many numbers in array

python

primes

generator

python-2.7