不管是在學習或者生活中，我們經常會遇到要求兩個數的最大公約數的問題。
最大公約數
那麼，什麼是公約數？什麼是最大公約數？
公約數，顧名思義，就是能被兩個數同時整除的一些數。而最大公約數就是這些數中的最大值。
舉個例子，比如我們要求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。
在計算較大數的最大公約數時，歐幾裡得算法是很高效的。
這就是今天的全部內容，覺得有用可以點個讚！