最大公约数怎么求算法

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

质数分解法

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

辗转相除法

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

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

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