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.

Waine

Have you tried this code for small numbers? If you want to use big numbers you should try gmplib.org library. There are a Python wrappers for this library and it worked fine for me. – Patter

Yeah the code works fine for smaller numbers. I checked the primes between 1 and 100 with it and it was correct. Thanks for the link though, I'll check it out. – Waine

There are a number of ways of getting to larger primes quickly using this algorithm discussed here: #2897797 – Centiare

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.

Infusorian

for python3 it is sys.maxsize instead of sys.maxint – Hawser

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.

Smearcase