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

如何修复我的错误？

如果您知道一种更好的方法来生成大质数，那将非常有帮助。

- user583507

---

你尝试过这段代码处理小数字吗？如果你想要处理大数字，你应该尝试使用http://gmplib.org/库。这个库有Python的包装器，对我来说效果很好。 - Elalfer

是的，这段代码对于较小的数字运行良好。我用它检查了1到100之间的质数，结果是正确的。不过还是谢谢你提供的链接，我会去看看的。 - user583507

有许多方法可以使用此处讨论的算法快速获取更大的质数：https://dev59.com/k3E85IYBdhLWcg3wMQhm - Scott Griffiths

Answer 1

以下代码演示了你遇到的问题：

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 异常。

- Justin Peel

---

在Python3中，用于表示最大整数值的常量是sys.maxsize而不是sys.maxint。 - ead

Answer 2

第5行试图分配一个充满True值的非常长的列表。可能您的lng太大而无法将该列表放入内存中？

我无法精确重现您的错误；在最坏的情况下，我只得到了一个MemoryError。

可能算法是正确的（虽然我不能打赌），只需尝试较小的数字即可。

- 9000