Python 2.7.6(64位)素性测试溢出错误

Question

我正在运行以下代码，这是一个4GBRAM的计算机上的win8上的Python2.7.664位版本的erathosthene筛子。

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。但有一种方法可以绕过这一点。To quote the docs:

CPython实现细节: xrange()的目的是简单和快速。实现可能会施加限制来实现这一点。Python的C实现将所有参数限制为本机longs (“短”Python整数)，并且还要求元素的数量适合本机longs。如果需要更大的范围，可以使用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):
    ...