不管是在學習或者生活中，我們經常會遇到要求兩個數的最大公約數的問題。

最大公約數

那麼，什麼是公約數？什麼是最大公約數？

公約數，顧名思義，就是能被兩個數同時整除的一些數。而最大公約數就是這些數中的最大值。

舉個例子，比如我們要求96和50的最大公約數。

應該怎麼做呢？

首先，我們要將96和50分別進行質因式分解，也就是將它們寫成質數乘積的形式。

那何為質數？

質數，又叫素數。指只能被自身和1整除的數。

那麼96=2x2x2x2x2x3, 50=2x5x5

然後，找出質因式中二者共同的質數。對比上面兩個式子，我們發現二者共同的只有2.

因此，96和50的最大公約數就是2.

如果兩個數相同的質因數多於1個呢？那麼最大公約數就是這些質因數的乘積。

再來舉個例子，我們要求90和50的最大公約數。

90=2·3·3·5, 50=2·5·5

二者相同的質因數有2和5，因此它們的最大公約數就是2·5=10.

上面介紹的是我們傳統的方法，好像也沒什麼問題，操作起來也簡單。

但這隻適用於比較小的數字，如果數字很大，那麼用這種方法就會費時又費力。

這時，就需要用到一個世界上最古老的算法——歐幾里得算法了。

歐幾里得算法

歐幾里得算法，就叫輾轉相除法。因為最早被發現記錄於歐幾里得的著作中，因此就以其名字來命名。這個算法就是用來求兩個數的最大公約數的。

接下來，我們就來看看歐幾里得算法的具體步驟。

比如我們要求1234和678的最大公約數。

首先，我們要計算1234 mod 678，這個mod是取餘運算符，這個式子的結果就是1234除以678的餘數。

即1234 mod 678 = 556

繼續計算678 mod 556 = 122

繼續556 mod 122 = 68

繼續122 mod 68 = 54

繼續68 mod 54 = 14

繼續54 mod 14 = 12

繼續14 mod 12 = 2

繼續12 mod 2 = 0

當所得的餘數為0時，最後一次運算中的除數就是我們要求的最大公約數。

因此，1234和678的最大公約數就是2。

原理解析

那麼，為什麼上面運算的結果就會得到最大公約數呢？

我們畫個圖來說明。

如圖，我們分別用對應長度的線段來表示1234和678。

我們並不知道最大公約數是多少，但我們知道的是這兩個數一定是最大公約數的整數倍。

這裡我們設最大公約數為k，那麼就可以把線段等分成很多小份，每一份的長度為k。

那麼，1234除以678的餘數556自然也可以用刻度為k的小段來構成。

同理，678除以556的餘數122同樣可以用刻度為k的小段來構成。

如此循環下去，直到只有1個線段k，此時餘數為0。對應的線段長度就是最大公約數2。

在計算較大數的最大公約數時，歐幾里得算法是很高效的。

這就是今天的全部內容，覺得有用可以點個贊！