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.

Have you tried this code for small numbers? If you want to use big numbers you should try http://gmplib.org/ library. There are a Python wrappers for this library and it worked fine for me. — Elalfer, Jan 20 '11 at 19:46
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. — , Jan 20 '11 at 19:48
There are a number of ways of getting to larger primes quickly using this algorithm discussed here: http://stackoverflow.com/questions/2897297/speed-up-bitstring-bit-operations-in-python — Scott Griffiths, Jan 20 '11 at 23:52

score 20 · Accepted Answer · answered Jan 21 '11 at 01:05

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.

for python3 it is `sys.maxsize` instead of `sys.maxint` – ead Mar 15 '18 at 20:33 — ead, Mar 15 '18 at 20:33

score 1 · Answer 2 · answered Jan 20 '11 at 19:55

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.

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

2 Answers2

Linked

Related