原標(biāo)題：要求最大公約數(shù)是什么含義（要求的含義是什么意思）

　　最大公約數(shù)

要求最大公約數(shù)是什么含義

　　那么，什么是公約數(shù)？什么是最大公約數(shù)？

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

　　含義

　　舉個(gè)例子，比如我們要求96和50的最大公約數(shù)。

要求的含義是什么意思

　　應(yīng)該怎么做呢？

　　首先，我們要將96和50分別進(jìn)行質(zhì)因式分解，也就是將它們寫(xiě)成質(zhì)數(shù)乘積的形式。

　　那何為質(zhì)數(shù)？

　　質(zhì)數(shù)，又叫素?cái)?shù)。指只能被自身和1整除的數(shù)。

　　那么96=2x2x2x2x2x3, 50=2x5x5

　　然后，找出質(zhì)因式中二者共同的質(zhì)數(shù)。對(duì)比上面兩個(gè)式子，我們發(fā)現(xiàn)二者共同的只有2.

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

　　如果兩個(gè)數(shù)相同的質(zhì)因數(shù)多于1個(gè)呢？那么最大公約數(shù)就是這些質(zhì)因數(shù)的乘積。

　　再來(lái)舉個(gè)例子，我們要求90和50的最大公約數(shù)。

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

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

　　上面介紹的是我們傳統(tǒng)的方法，好像也沒(méi)什么問(wèn)題，操作起來(lái)也簡(jiǎn)單。

　　但這只適用于比較小的數(shù)字，如果數(shù)字很大，那么用這種方法就會(huì)費(fèi)時(shí)又費(fèi)力。

　　這時(shí)，就需要用到一個(gè)世界上最古老的算法——?dú)W幾里得算法了。

　　歐幾里得算法

　　歐幾里得算法，就叫輾轉(zhuǎn)相除法。因?yàn)樽钤绫话l(fā)現(xiàn)記錄于歐幾里得的著作中，因此就以其名字來(lái)命名。這個(gè)算法就是用來(lái)求兩個(gè)數(shù)的最大公約數(shù)的。

　　

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

公約

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

　　首先，我們要計(jì)算1234 mod 678，這個(gè)mod是取余運(yùn)算符，這個(gè)式子的結(jié)果就是1234除以678的余數(shù)。

　　即1234 mod 678=556

　　繼續(xù)計(jì)算678 mod 556=122

　　繼續(xù)556 mod 122=68

　　繼續(xù)122 mod 68=54

　　繼續(xù)68 mod 54=14

　　繼續(xù)54 mod 14=12

　　繼續(xù)14 mod 12=2

　　繼續(xù)12 mod 2=0

　　當(dāng)所得的余數(shù)為0時(shí)，最后一次運(yùn)算中的除數(shù)就是我們要求的最大公約數(shù)。

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

　　原理解析

　　那么，為什么上面運(yùn)算的結(jié)果就會(huì)得到最大公約數(shù)呢？

　　我們畫(huà)個(gè)圖來(lái)說(shuō)明。

　　

　　如圖，我們分別用對(duì)應(yīng)長(zhǎng)度的線段來(lái)表示1234和678。

　　我們并不知道最大公約數(shù)是多少，但我們知道的是這兩個(gè)意思數(shù)一定是最大公約數(shù)的整數(shù)倍。

　　這里我們?cè)O(shè)最大公約數(shù)為k，那么就可以把線段等分成很多小份，每一份的長(zhǎng)度為k。

　　

　　那么，1234除以678的余數(shù)556自然也可以用刻度為k的小段來(lái)構(gòu)成。

　　

　　同理，678除以556的余數(shù)122同樣可以用刻度為k的小段來(lái)構(gòu)成。

　　如此循環(huán)下去，直到只有1個(gè)線段k，此時(shí)余數(shù)為0。對(duì)應(yīng)的線段長(zhǎng)度就是最大公約數(shù)2。

　　

　　在計(jì)算較大數(shù)的最大公約數(shù)時(shí)，歐幾里得算法是很高效的。