如果阵列中的数字太多,则素数生成器会因内存错误而崩溃

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(我认为),它将从内存错误中崩溃.我无法弄清楚如何扩展它使用的内存,以便它可以占用所需的内存.任何建议将不胜感激!

我的问题与此问题非常相似,但这是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不能再解决它).我知道我是n(最大)的平方根,但是在那么大的数字上并没有太大的区别.

如果可行并且在硬盘驱动器上安全,则必须将此计算拆分为较小的部分.这使得该过程变慢,但可行.