Python OverflowError: не может поместиться 'long' в целое число с размером индекса

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

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

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

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


python rsa primes
person Community    schedule 20.01.2011    source источник
comment
Вы пробовали этот код для небольших чисел? Если вы хотите использовать большие числа, попробуйте библиотеку gmplib.org. Для этой библиотеки есть оболочки Python, и у меня она отлично сработала.   -  person Elalfer    schedule 20.01.2011
comment
Да, код отлично работает для меньших чисел. Я проверил с его помощью простые числа от 1 до 100, и все оказалось правильно. Хотя спасибо за ссылку, проверю.   -  person    schedule 20.01.2011
comment
Существует несколько способов быстрого перехода к большим простым числам с использованием этого алгоритма, обсуждаемого здесь: stackoverflow.com/questions/2897297/   -  person Scott Griffiths    schedule 21.01.2011

Ответы (2)


arrow_upward
19
arrow_downward

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

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, если это не сработает.

person Justin Peel    schedule 21.01.2011
comment
для python3 это sys.maxsize вместо sys.maxint - person ead; 15.03.2018

arrow_upward
1
arrow_downward

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

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

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

person 9000    schedule 20.01.2011