Ошибка переполнения Python 2.7.6(64-битная) при тестировании простоты

Question

Я запускаю следующий код, который является версией сита erathosthene в Python 2.7.6 64-разрядной на win8 на компьютере с 4 ГБ ОЗУ.

def erathosthenes_sieve2(n):
    '''Tests n>1 primality using improved erathostene's method'''  
    if n==2:  
        return True          
    if n%2==0:  
        return False          
    limit=long(math.floor(math.sqrt(n)))  
    for i in xrange(3,limit+1,2):  
       if n%i==0:  
           return False   
    return True  

Когда я вызываю эту функцию для достаточно больших чисел, например 48112959837082048697(это простое число), я получаю следующую ошибку.

erathosthenes_sieve2(48112959837082048697)  
---------------------------------------------------------------------------
OverflowError                             Traceback (most recent call last)
<ipython-input-28-b0a5b24a8b94> in <module>()
----> 1 erathosthenes_sieve2(48112959837082048697)

D:\repos\PrimalityTests\Eratosthenes2.py in erathosthenes_sieve2(n)
      9         return False
     10     limit=long(math.floor(math.sqrt(n)))
---> 11     for i in xrange(3,limit+1,2):
     12        if n%i==0:
     13            return False

OverflowError: Python int too large to convert to C long

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

Answer 1

Проблема в том, что xrange занимает C longэто означает, что вы не можете иметь произвольную точность int, Но есть способ обойти это. Цитировать документы:

Детали реализации CPython: xrange() должен быть простым и быстрым. Реализации могут налагать ограничения для достижения этой цели. Реализация Python на C ограничивает все аргументы собственными длинными C-символами ("короткими" целыми числами Python), а также требует, чтобы количество элементов соответствовало собственным длинным C-символам. Если требуется больший диапазон, можно создать альтернативную версию с помощью модуля itertools:

islice(count(start, step), (stop-start+step-1+2*(step<0))//step)

Итак, в вашем случае:

for i in islice(count(3, 2), ((limit+1)-3+2-1+2*(2<0))//2):
    ...