要求最大公約數是什么含義（要求的含義是什么意思）

原標題：要求最大公約數是什么含義（要求的含義是什么意思）

　　最大公約數

要求最大公約數是什么含義

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

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

　　含義

　　舉個例子，比如我們要求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。

　　

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