Python OverflowError: не может вписать long в целое число index = size

Question

Я хочу сгенерировать два действительно больших простых числа, используя алгоритм, который я нашел в сети и немного изменил.

Я получаю эту ошибку в строке 5:

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

Мой код:

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

Как я могу исправить мою ошибку?

Если вы знаете лучший способ генерирования больших простых чисел, это также будет полезно.

Answer 1

Следующий код демонстрирует проблему, с которой вы столкнулись:

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

, что дает OverflowError. Если вы вместо этого сделаете:

x = [True]*(sys.maxint)

тогда вы должны получить MemoryError.

Вот что происходит. Python может обрабатывать произвольно большие целые числа со своим собственным расширяемым типом данных. Однако, когда вы пытаетесь создать список, как описано выше, Python пытается преобразовать число повторений небольшого списка, который является целым числом Python, в целое число C типа Py_ssize_t. Py_ssize_t определяется по-разному в зависимости от вашей сборки, но может быть ssize_t, long или int. По сути, перед выполнением преобразования Python проверяет, может ли целое число Python вписаться в целочисленный тип C, и выдает ошибку OverflowError, если она не работает.

Answer 2

Строка 5 верна для выделения действительно длинного списка, полного True значений.Возможно, ваш lng слишком велик, чтобы вместить этот список в память?

Я не смог точно воспроизвести вашу ошибку;в худшем случае я получил MemoryError.

Возможно, алгоритм в порядке (хотя я не могу поспорить), просто попробуйте меньшее число.