Python溢出错误：无法将'long'放入索引大小的整数中

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

第5行试图创建一个很长的列表，里面全是True值。可能你的lng值太大了，导致无法在内存中放下这个列表？

我没能完全复现你的错误；在最糟糕的情况下，我只遇到了一个MemoryError。

算法可能没问题（虽然我不能保证），你可以试试用一个更小的数字。

Answer 2

下面的代码展示了你遇到的问题：

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错误。