python - 为什么这是费马因式分解的错误实现？

我目前正在通过 Project Euler，这是我在问题 3 中的尝试(在 Python 中)。我运行了它并让它运行了大约 30 分钟。在此之后，我查看了“sum”下的数字。我发现了几个问题:其中一些数字是偶数，因此不是质数，其中一些数字甚至不是 n 的适当因数。当然，它们仅相差 0.000001(通常除法产生 x.99999230984 或其他)。我最终停下来的号码是 3145819243.0。

谁能解释为什么会发生这些错误？

编辑:我对定理的解释基本上是，通过重新排列变量，您可以用 n + y^2 的平方根求解 x，并且 y 将被强制执行直到它是一个整数。在此之后，实际的质因数将是 x+y。

这是我的代码。

import math
n = int(600851475143)
y = int(1)
while y >= 1:
    if math.sqrt(n + (y**2)).is_integer():
        x = math.sqrt(n + (y**2))
        print "x"
        print x
        print "sum"
        print x + y
        if x + y > (600851475142/2):
            print "dead"
        else:
            print "nvm"
    y = y + 1

最佳答案

大数和浮点精度的典型问题。

当您到达 y = 323734167 时，您计算 math.sqrt(n + y**2) ，即 math.sqrt(104804411734659032) 。

这是根据 wolfram alpha 的 3.23735095000000010811308548429078847808587868214170702... × 10^8，即不是整数，而是根据 python 的 323735095.0。

如您所见，python 没有看到 .00000001... 的精度。

您可以测试结果的平方，而不是测试 is_integer :

 > 323735095 ** 2
=> 104804411734659025

并查看它是否与输入匹配(它不匹配，输入是 104804411734659032 ，关闭 7)。

关于python - 为什么这是费马因式分解的错误实现？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43815847/