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

求最大公約數(shù)有多種方法，常見的有質(zhì)因數(shù)分解法、短除法、輾轉(zhuǎn)相除法、更相減損法。如果有一個(gè)自然數(shù)a能被自然數(shù)b整除，則稱a為b的倍數(shù)，b為a的約數(shù)。幾個(gè)自然數(shù)公有的約數(shù)，叫做這幾個(gè)自然數(shù)的公約數(shù)。公約數(shù)中最大的一個(gè)公約數(shù)，稱為這幾個(gè)自然數(shù)的最大公約數(shù)。

輾轉(zhuǎn)相除法

使用到的原理很聰明也很簡單，假設(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）（y>0），如此便可把原問題轉(zhuǎn)化為求兩個(gè)更小數(shù)的最大公約數(shù)，直到其中一個(gè)數(shù)為0，剩下的另外一個(gè)數(shù)就是兩者最大的公約數(shù)。

例如，12和30的公約數(shù)有：1、2、3、6，其中6就是12和30的最大公約數(shù)。