最大公约数怎么求算法

计算最大公约数,可采用多种方法,质因数分解法、短除法、辗转相除法及更相减损法均为常见手段。若自然数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的最大公约数。