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

Question

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.

Answer 1

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.

Answer 2

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.