最大公約數(shù)怎么求算法

2025-06-08 17:51:45文/趙國海

計(jì)算最大公約數(shù),可采用多種方法,質(zhì)因數(shù)分解法、短除法、輾轉(zhuǎn)相除法及更相減損法均為常見手段。若自然數(shù)a能被自然數(shù)b整除,則a稱為b的倍數(shù),而b為a的約數(shù)。幾個(gè)自然數(shù)共有的約數(shù),被定義為這幾個(gè)自然數(shù)的公約數(shù)。而在這些公約數(shù)中,最大的一個(gè)便被稱為這幾個(gè)自然數(shù)的最大公約數(shù)。

最大公約數(shù)怎么求算法

輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法的原理既巧妙又簡(jiǎn)潔。我們?cè)O(shè)f（x,y）代表x和y的最大公約數(shù),取k=x/y,b=x%y,由此可得x=ky+b。若一個(gè)數(shù)能同時(shí)整除x和y,那么它也必能同時(shí)整除b和y；反之,能同時(shí)整除b和y的數(shù),也必能同時(shí)整除x和y。這意味著x和y的公約數(shù)與b和y的公約數(shù)是完全相同的,它們的最大公約數(shù)也相同。因此,我們有f（x,y）=f（y,x%y）（當(dāng)y>0時(shí)）。這樣,原問題就轉(zhuǎn)化為求兩個(gè)更小數(shù)的最大公約數(shù),這一過程持續(xù)進(jìn)行,直至其中一個(gè)數(shù)變?yōu)?,此時(shí)剩下的另一個(gè)數(shù)便是兩者的最大公約數(shù)。

以12和30為例,它們的公約數(shù)有1、2、3、6,其中6便是12和30的最大公約數(shù)。

分享到

推薦閱讀