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

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

Я получаю эту ошибку в строке 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

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

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

Ответы

Ответ 1

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

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

что дает a OverflowError. Если вы сделаете следующее:

x = [True]*(sys.maxint)

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

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

Ответ 2

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

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

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