|
最大公約數，Greatest Common Divisor(GCD)，當然你要是叫它Highest Common Factor(HCF)也沒人會說不行。 相信提到最大公約數大家都不會陌生，因為從小學開始我們就接觸到了， 短除法對吧！大概是這樣的：如果我們拿到的數是103287和417145，我們還可以通過短除法輕松的解決嗎？ 所以要給大家介紹兩種新的求法，第一種的思維過程很簡單，窮舉法，思路就是枚舉每一個數，如果兩個數字都可以整除就說明這個是公因數，最大公因數當然要從大往小舉了！從兩個數的較小值到1。有一個符合就可以聽停止了。 我們看到就算要求的a和b很大也可以輕松求解。 很明顯，這個算法的事件復雜度是O(min(a,b))，線性的時間復雜度。接下來要介紹的輾轉相除法效率就更高了。  轉轉相除法 用較小數除較大數，再用出現的余數（第一余數）去除除數，再用出現的余數（第二余數）去除第一余數，如此反復，直到最后余數是0為止。 關于它的證明......感興趣的人看一下吧 設兩數為a、b(a>b)，用gcd(a,b)表示a，b的最大公因數，r=a (mod b) 為a除以b的余數，k為a除以b的商，即a/b = k······r。輾轉相除法即是要證明 gcd(a,b)=gcd(b,r)。 第一步：令 第二步：根據前提可知 第三步：根據第二步結果可知， 第四步：可以斷定 不知道你有沒有看懂。不過不重要我們來看代碼吧。 
. |
|
|
，則設
也是
的因數
與
