Python OverflowError: cannot fit 'long' into an index=sized integer

I want to generate two really large prime numbers using an algorithm I found online and changed slightly.

I get this error on line 5:

Python OverflowError: cannot fit 'long' into an index=sized integer 

My code:

import math def atkin(end): if end < 2: return [] lng = ((end/2)-1+end%2) **sieve = [True]*(lng+1)** for i in range(int(math.sqrt(end)) >> 1): if not sieve[i]: continue for j in range( (i*(i + 3) << 1) + 3, lng, (i << 1) + 3): sieve[j] = False primes = [2] primes.extend([(i << 1) + 3 for i in range(lng) if sieve[i]]) return primes 

How can I fix my error?

If you know a better way to generate large primes, that would be helpful also.

2 Answers

The following code demonstrates the problem that you are running into:

import sys x = [True]*(sys.maxint+1) 

which yields an OverflowError. If you instead do:

x = [True]*(sys.maxint) 

then you should get a MemoryError.

Here is what is going on. Python can handle arbitrarily large integers with its own extendible data type. However, when you try to make a list like above, Python tries to convert the number of times the small list is repeated, which is a Python integer, to a C integer of type Py_ssize_t. Py_ssize_t is defined differently depending on your build but can be a ssize_t, long, or int. Essentially, Python checks if the Python integer can fit in the C integer type before doing the conversion and raises the OverflowError if it won't work.

Line 5 trues to allocate a really long list full of True values. Probably your lng is too large to fit that list in memory?

I was not able to exactly reproduce your error; in the worst case I ended up with just a MemoryError instead.

Probably the algorithm is ok (though I can't bet), just try a smaller number.