Python 溢出错误 : cannot fit 'long' into an index=sized integer

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 整数类型，如果不工作则引发 OverflowError。