为什么这是Fermat因式分解的不正确实现?

我目前正在研究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

最佳答案

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

当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).