Python OverflowError:不能使'long'适合index =大小的整数

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.