Python OverflowError:无法将“long”放入index=size整数中

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

下面的代码演示了您遇到的问题：

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

它产生一个OverflowError。如果你这样做了：

x = [True]*(sys.maxint)

然后你应该得到一个MemoryError。

这是发生的事情。Python可以使用自己的可扩展数据类型处理任意大的整数。但是，当您尝试创建一个类似于上面的列表时，Python会尝试将小列表的重复次数（Python整数）转换为Py_ssize_t类型的C整数。Py_ssize_t根据您的构建定义不同，但可以是ssize_t、long或int，在执行转换之前，Python检查Python整数是否适合C integer类型，如果不起作用，则引发OverflowError。