Joseph Farah - 2 years ago 62
Python Question

# 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())
``````

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!

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

EDIT: 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
``````

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