Python:检查(非常大的)素数时为 "long int too large to convert to float"

Question

我尝试从这个答案中实现第一个 is_prime 函数: https://stackoverflow.com/a/17298131/6208280

# for large numbers, xrange will throw an error.
# OverflowError: Python int too large to convert to C long
# to get over this:

def mrange(start, stop, step):
    while start < stop:
        yield start
        start += step

# benchmarked on an old single-core system with 2GB RAM.

from math import sqrt

def is_prime(num):
    if num == 2:
        return True
    if (num < 2) or (num % 2 == 0):
        return False
    return all(num % i for i in mrange(3, int(sqrt(num)) + 1, 2))

但是我在测试高数字时遇到了一点问题。

对于非常大的数字，我得到一个溢出错误:long int too large to convert to float

我检查了 float 的最大值:

sys.float_info.max
1.7976931348623157e+308

对于 is_prime(10**308) 一切正常...但是例如对于 is_prime(10**309) 会有这个溢出错误(因为 float 最大值？)。

这是否意味着 1.7976931348623157e+308 是这种 is_prime() 函数的限制，或者是否有任何解决方案可以使用 is_prime() 函数检查更大的数字？

在我看来，“使用小数点”这样的解决方案并不能真正解决问题，因为素数检查函数需要精度不够？

Answer 1

如果你需要 float 的唯一原因是能够做到 int(sqrt(num)) , 你可以找到一个相当有效的 intsqrt功能并改用它。参见 this question ，以及从已接受的答案链接的博客文章，以获取一些想法。

---

或者您可以只更改您的代码，这样它就不需要 sqrt根本。例如，而不是以 int(sqrt(num))+1 结尾的范围, 你可以使用 takewhile 测试lambda i: i*i <= num .或者，既然你已经得到了 mrange功能:

def sqrmrange(start, sqrstop):
    while start*start < sqrstop:
        yield start
        start += step

或者，如果您不需要它成为单行代码，您可以写一些比其中任何一个都更不抽象(并且可能更有效？)的东西。 (但实际上，任何 intsqrt 都可能比最好的 **2 测试更快，因为您只需在循环开始时执行一次 intsqrt，而不是每次循环都执行。)

---

或者，如果你真的想保持这种结构，你可以使用 decimal .你说:

In my mind such solutions as "use decimal" will not really solve the problem, because of the lack of precision a prime number checking function will need?

但这是不对的。使用 float意味着您本质上仅限于 52 位精度，如果在您溢出之前很久就出现问题。使用 decimal意味着您可以获得所需的精度位数——即使是默认的 30 位也已经远远超过 52 位。例如:

>>> float(10**20) == float(10**20)+1
True
>>> Decimal(10**20) == Decimal(10**20)+1
False

(事实上，由于您是从一个巨大的 Decimal 构造 int 的，它会自动扩展以跟踪 int 所需的尽可能多的数字……但您仍然需要设置在调用 sqrt 之前的精度。)

以编程方式计算和设置操作所需的精度可能很复杂，但在这种情况下，它非常简单。更大的问题是真的很大Decimals比真正的大整数慢很多。