? ——? 首先，我只想說(shuō)，我小學(xué)還學(xué)過(guò)這個(gè)?。。?/p>

先來(lái)介紹一下輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法又叫歐幾里得算法,是歐幾里得最先提出來(lái)的.輾轉(zhuǎn)相除法的實(shí)現(xiàn),是基于下面的原理(在這里用(a,b)表示a和b的最大公因數(shù))：

　　(a,b)=(a+b,b)=(a,ka+b),其中a、b、k都為自然數(shù).………………①

? ? ? ?PS: (a,b)=(a-b,b)=(a,ka-b),可加亦可減

　　也就是說(shuō),兩個(gè)數(shù)的最大公約數(shù),將其中一個(gè)數(shù)加到另一個(gè)數(shù)上,得到的新數(shù),其公約數(shù)不變,比如(4,6)=(4+6,6)=(4,6+2×4)=2.

證明：

如果p是a和ka+b的公約數(shù),p整除a,也能整除ka+b.那么就必定要整除b,所以p又是a和b的公約數(shù),從而證明他們的最大公約數(shù)也是相等的.

　　基于上面的原理,就能實(shí)現(xiàn)我們的迭代相減法：

　　(78,14)=(64,14)=(50,14)=(36,14)=(22,14)=(8,14)=(8,6)=(2,6)=(2,4)=(2,2)=(0,2)=2

　　思路很簡(jiǎn)單，看了就懂? ? ? ?

????? ?在上面的過(guò)程中,由(78,14)到(8,14)完全可以一步到位,因?yàn)?78,14)=(14×5+8,14)=(8,14),由此就誕生出我們的輾轉(zhuǎn)相除法：

????? ?求法如下

????????*(1)用大的數(shù)對(duì)小的數(shù)求余

????????*(2)把小的數(shù)賦值給大的數(shù)，把求余獲得的結(jié)果賦值給小的數(shù)，

????????*(3)循環(huán)上一步的操作，直到求余的結(jié)果為零

????????*(4)上一步被求余的數(shù)就是我們要的最大公約數(shù)，不信的話，你可以動(dòng)手試試

　　迭代相減法和輾轉(zhuǎn)相除法在本質(zhì)上是一樣的,相對(duì)來(lái)說(shuō),減法比較簡(jiǎn)單,但是除法步數(shù)少.

其實(shí)最大公約數(shù)還有更相減損術(shù)和Stein算法，但是我不想學(xué)啦！