爲什麼這是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因式分解的錯誤實現？

回答

相關問題