最大公约数怎么求算法

【最大公约数怎么求算法】
求最大公约数有多种方法,常见的有质因数分解法、短除法、辗转相除法、更相减损法 。如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数 。几个自然数公有的约数,叫做这几个自然数的公约数 。公约数中最大的一个公约数,称为这几个自然数的最大公约数 。
辗转相除法使用到的原理很聪明也很简单,假设用f(x,y)表示x,y的最大公约数,取k=x/y,b=x%y,则x=ky b,如果一个数能够同时整除x和y,则必能同时整除b和y;而能够同时整除b和y的数也必能同时整除x和y,即x和y的公约数与b和y的公约数是相同的,其最大公约数也是相同的,则有f(x,y)=f(y,x%y)(y>0),如此便可把原问题转化为求两个更小数的最大公约数,直到其中一个数为0,剩下的另外一个数就是两者最大的公约数 。
例如,12和30的公约数有:1、2、3、6,其中6就是12和30的最大公约数 。

    推荐阅读