如果数组中的数字过多，质数发生器会因内存错误而崩溃 [英] Prime number generator crashes from memory error if there are too many numbers in array

问题描述

我有一个质数生成器，我很好奇我能基于优化等方法使质数生成器变小又快:

I have a prime number generator, I was curious to see how small and how fast I could get a prime number generator to be based on optimizations and such:

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(我认为)，它将因内存错误而崩溃.我不知道如何扩展它使用的内存，以便它可以占用所需的内存.任何建议将不胜感激！

The generator works great! It is super fast, feel free to try it out. However, if you input numbers greater than 10^9 or 10^10 (i think) it will crash from a memory error. I can't figure out how to expand the memory it uses so that it can take as much as it needs. Any advice would be greatly appreciated!

我的问题与这很相似一个，但这是Python，而不是C.

My question is very similar to this one, but this is Python, not C.

这是我尝试运行10 ^ 9时获得的与内存相关的回溯之一.

This is one of the memory related tracebacks I get for trying to run 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

推荐答案

问题在第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的平方根(最大值)是多少，但是在这么大的范围内，相差不大.

1000000000^1000000000 is a 9 * 10^9 digit long number. Storing it takes multiple Gb if not Tb (WolframAlpha couldn't caclulate it anymore). I know that i ist the square root of n (maximal), but at that large numbers that's not a big difference.

如果可能的话，您必须将这种计算分解为较小的部分，并将其安全地保存在硬盘驱动器上.这会使该过程缓慢但可行.

You have to split this caclulation into smaller parts if posible and safe it on a hard drive. This makes the process slow, but doable.

这篇关于如果数组中的数字过多，质数发生器会因内存错误而崩溃的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！