最大公约数怎么求算法

最大公约数求法有很多，接下来介绍三种方法。

质数分解法

1、把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数。

2、求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×524与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以24和60的最大公约数是12。

3、质数分解法是其他方法的基础，一定要熟练掌握，知道质数分解法的原理。

短除法

1、短除法的本质是质数分解法。短除法求解先用两个数的公约数去除，一直除到两个商互质，再讲所有的公约数想乘，就可以得到最大公约数。

2、短除法简单易懂，计算方便，但是短除法求的数太多、太大时就有些笨重。

3、求18和30 的最大公约数，先用2除，再用3除，最后得到3和5,3和5互质，不能再除，所以最大公约数等于2*3=6。

辗转相除法

1、辗转相除法是求两个自然数的最大公约数的一种方法，也叫欧几里德算法。

2、用较大数除以较小数，再用出现的余数去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。最后为0，则除数为最大公约数。

3、依然是求18和30 的最大公约数，方法如图所示。