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

我目前正在通过项目欧拉，这是我的尝试（在Python中）在问题3。我跑这个，让它大约30分钟。在此之后，我查看了“总和”下的数字。我发现了几个问题：其中一些数字是偶数，因此不是素数，其中一些数字甚至不是n的适当因素。当然，他们只有0.000001（通常部门产生x.99999230984或其他）。我最终停在的号码是3145819243.0。为什么这是Fermat因式分解的错误实现？

任何人都可以解释为什么会出现这些错误？

编辑：我对该定理的解释基本上是，在重新排列变量的情况下，可以用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

来源

2017-05-06 Liam Wilson

我给你一个提示：[筛分算法]（https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）这将拯救你的生命与这项挑战Projecteuler和其他许多人在那里。如果你发现它很困难，我可以使用'Sieve算法'发布我对这个问题的答案。否则，请尝试一下，这是最好的做法。另外，请记住一件事：Projecteuler的问题必须在不到一分钟内解决。如果不是，你必须改变你的方法/算法/思维方式。 –

@ChihebNexus筛是好的，但理解为什么这种不同方法的实施不起作用甚至更好。欧拉项目的时间也没有限制。如果你想用暴力方法，为什么不呢？ – njzk2

@ njzk2是的，你在这里有一点。 –

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

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

这是3.23735095000000010811308548429078847808587868214170702... × 10^8根据wolfram alpha，即不是整数，但根据python 323735095.0。如你所见，python没有精确度来看.00000001...。

不检测is_integer，你可以测试结果的平方：

> 323735095 ** 2 
=> 104804411734659025

，看看它是否在输入（不，输入为104804411734659032，关闭的7）相匹配。

来源

2017-05-06 02:09:33 njzk2

哦，好的。除此之外，实施是正确的？ –

有优化的空间，但它看起来像是一个有效的实现fermat的分解。不过，你必须找到更好的平方根。 – njzk2

（参见http://stackoverflow.com/questions/30490439/how-to-take-square-root-of-large-numbers-in-python） – njzk2

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

回答

相关问题