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

Question

我目前正在通过Project Euler进行工作，这是我在问题3处的尝试(在Python中(。我跑了，让它大约30分钟。之后，我查看了"总和"下的数字。我发现了几个问题：其中一些数字甚至不是素数，因此其中一些数字甚至不是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

Answer 1

典型的问题，具有大数字和浮点精度。

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

这是3.23735095000000010811308548429078847808587868214170702... × 10^8根据Wolfram Alpha，即不是整数，而是323735095.0根据Python。

如您所见，Python没有观看.00000001...的精确度。

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

 > 323735095 ** 2
=> 104804411734659025

看看它是否与输入匹配(不匹配输入，输入为 104804411734659032，以7(。