12 和 18 的最大公約數是多少？

最大公約數：最大公約數，也稱最大公因數、最大公因子，指兩個或多個整數共有約數中最大的一個。例如：18 與 12 的最大公約數為 6 。

短除法短除法是求最大公因數的一種方法：先把每個數的因數找出來，然後再找出公因數，最後在公因數中找出最大公因數。

因式分解法

在初中數學題中，基本上我們就是採取因式分解或者短除法的形式來求最大公約數。

但是它們存在的問題是：當公共素因子較小時，通過觀察可以很快找出；但是當公因子較大時，僅僅通過觀察已經很難找出甚至在一定時間內找不出。

比如求 22008 和 655 的最大公約數時，很難直接找到其公因子。

那麼有沒有更好的方法來求解最大公約數呢？答案是有的，就是接下來要介紹的歐幾里得算法。

歐幾里得算法

歐幾里得算法（英語：Euclidean algorithm），又稱 輾轉相除法，是求最大公約數的算法。

輾轉相除法基於如下原理：兩個整數的最大公約數等於其中較小的數和兩數的差的最大公約數。

輾轉相除法首次出現於歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至東漢出現的《九章算術》。

輾轉相除法基於如下原理：兩個整數的最大公約數等於其中較小的數和兩數的差的最大公約數。例如，252 和 105 的最大公約數是 21；因為 252 − 105 = 21 × (12 − 5) = 147 ，所以 147 和 105 的最大公約數也是 21。

在這個過程中，較大的數縮小了，所以繼續進行同樣的計算可以不斷縮小這兩個數直至其中一個變成零。

這時，所剩下的還沒有變成零的數就是兩數的最大公約數。

將上面的較大的數縮小的過程中往往使用的是 MOD 操作。

MOD，是一個 數學運算符號-----求餘運算符。

例如 a mod b = c，表明 a 除以 b 餘數為 c 。 在整數的除法中，只有能整除與不能整除兩種情況，所以當不能整除時，就會產生餘數。

我們藉助於 MOD 使用 輾轉相除法的概念來求數字 1112和數字 695的最大公約數。

當餘數變為 0 的時候，最後一個操作的 除數是最大公約數，即 139是數字 1112和數字 695的最大公約數。

一般算法流程如下：

動畫理解

通過動畫來理解一下為什麼使用 輾轉相除法可以找到最大公約數。

將最大的公約數設置為 n，當然雖然一開始對於每個整數是不知道可以分段成多少個 n 的，但是，可以知道 1112 和 695 都是最大公約數 n 的倍數。

通過 mod 操作，不停的找餘數。

最後兩個數是倍數關係，可以整除，餘數為 0 ，結束了操作。

此時剩下的一條線段的長度就是 1112 和 695 的最大公因數。