偽從零開始學算法 - 2.2 求最大公約數

簡介

兩個或多個正整數數的公約數是，對於這些數，存在一個正整數，可以整除它們。公約數可能有若干個，而其中最大的就是最大公約數。

也就是：

A: card(A) ≥ 2, (66 a ∈ A, a ∈ N*) ;B = {n ∈ N*| 66 x ∈ A, x mod n = 0};k = max{B};k即為A中各數的最大公約數。

從人類的做法推導

我們計算最大公約數的時候，通常用短除法來計算。具體的方法是：同時讓這些數除以一個比較小的公約數，得到的結果再這樣操作，直到找不到大於等於2的公約數；將除數相乘即得到最大公約數。比如：

短除法計算最大公約數

通過經驗，人是可以快速找到一些較小的公約數，寫在除數上的。但是，計算機卻無法這麼做。但是計算機可以從1開始，判斷某個整數是否能整除所有給定的數。如果能，即為公約數，記下來；否則，除數加1，再試。

但是，算法是有限的，到什麼時候停止呢？根據常理，一組數的最大公約數一定不大於這組數的最小的數。因此，如果算到這組數的最小值的話，就不用再算下去了。

由此可以推導出流程圖如下：

計算最大公約數流程圖(1)

鑑於1能夠整除所有正整數，我們可以讓循環從2開始。這樣，流程圖如下：

計算最大公約數流程圖(2)

如果我們把「66 a ∈ A, a mod i = 0?」的判斷展開，則如下：

計算最大公約數流程圖(3)

已經非常複雜了。

實際應用中，我們更多的是計算兩個數之間的最大公約數。這樣，流程圖可以簡化如下：

計算兩個數的最大公約數流程圖

不過這個方法在計算的時候，如果是小的數字還可以，遇到大數的時候，計算時間就非常長。

這時候還可以使用更加簡便的算法。

輾轉相除法

輾轉相除法又稱歐幾裡得算法，首次出現於《幾何原本》中，被人們認為是史上第一個算法。它可以用於求兩數的最大公約數。

首先，用兩數中較大數除以較小數，求得數；再用較小數和餘數按上述操作進行相除；直到餘數為0。此時的除數即為最大公約數。

流程圖表示如下：

輾轉相除法(1)

考慮到許多程式語言使用的是DO-WHILE型的直到型循環結構，還有一些語言沒有直到型循環結構，流程圖改寫為如下：

輾轉相除法(2)

其中當型的流程圖在循環結構前有一個定義變量r的操作。這裡的r的賦值只要不等於0就可以了。

此外，還有遞歸型的流程圖：

輾轉相除法(遞歸)

更相減損術

更相減損術是《九章算術》中給出的求兩個數的最大公約數的方法：

可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。

算法描述為：

第一步：任意給兩個正整數；判斷它們是否都是偶數，如果是，用2約簡，並記下次數；否則，進行下一步；

第二步：以較大的數減去較小的數，把差與較小的數相比，並用大數減小數。繼續此操作，使所得數相等為止。記下這個數。

第三步：如果第一步有約簡，第二步所得的數乘上2乘約簡次數就是最大公約數。否則，第二步所得的數就是最大公約數。

（人教版的教科書上對這個的解釋有問題……粗體字表示增加的內容）

流程圖如下：

更相減損術(1)

標準化後如下：

更相減損術(2)

看起來非常麻煩。

不過，還有一個簡單的算法：

更相減損術(3)

實際上這和輾轉相除法很相似了。在維基百科上，它們是在一個詞條內的，而且上面的算法被稱為歐幾裡得算法的減法形式。

三者的比較

在現代，算法之間的比較主要體現在效率上。在下面，我將使用IPython的工具來測試它們的運行速度（使用語言為Python，在安裝Windows 10 專業版和Python 3.6的華碩N551ZU上進行，結果僅供參考）。

各種算法的執行時間測試

從這裡就能看出來，雖然現在電腦硬體水平的發展相當成熟，但是各個算法之間的運行速度還是有比較明顯的差別的。

之前的那個直接求最大公約數的方法，運算速度相對於其他的算法都比較慢，尤其是在兩個數都非常大的情況下。相比之下，其他算法的運算速度和它的運算速度相差懸殊。

另外，更相減損術在兩數相差懸殊的時候，運算速度也會減慢。

從這裡我們可以看出優化算法的意義——可以顯著減少運行時間，提高效率，節能。這個測試還是在比較好的機器上進行的，如果是在簡單的單片機上，差別就更加明顯了。

參考資料

如果大家想了解關於這兩個算法的更多內容，也可以看看。

輾轉相除法 - 維基百科，自由的百科全書普通高中課程標準實驗教科書（必修） 數學（A版） 必修3. 人民教育出版社輾轉相除法、更相減損法、Stein算法 - CSDN博客