设有两个正整数m和n,如何求其最大公约数

最大公约数（Greatest Common Divisor，简称GCD），也称最大公因数，是指两个或多个整数共有约数中最大的一个。设有两个正整数m和n，如何求它们的最大公约数呢？本文从多个角度对此进行分析。

一、质因数分解法

将m和n分别分解质因数，并找出它们共有的部分，然后将这些部分乘起来即为最大公约数。例如，对于20和30，它们的质因数分解分别为20=2*2*5，30=2*3*5，它们共有的部分为2*5=10，因此它们的最大公约数为10。

二、辗转相除法

这是一种更为简便的方法。将m与n中较小的数作为第一个数，较大的数作为第二个数。然后用第二个数除以第一个数，得到余数r1，将第一个数设为第二个数，将余数r1设为第一个数，重复上述步骤，直到余数为0为止。此时，第一个数即为最大公约数。例如，对于28和14，首先用28除以14，得到余数r1=0；再用14除以r1=0，得到最大公约数为14。

三、更相减损术

将m与n中较大的数减去较小的数，然后用得到的差值再次减去较小的数。一直重复，直到所减数相等为止，此时所得数即为最大公约数。例如，对于24和18，首先24-18=6，再次用18减去6，得到12；然后用6减去12，得到6；最后用12减去6，得到6，所得数即为最大公约数。

四、欧几里得算法

也称辗转相除法。欧几里得算法是辗转相除法的递归形式，是一种更为高效的求解最大公约数的算法，时间复杂度为O(logn)。步骤如下：

1. 用n除以m，得到余数r；

2. 若r=0，则m是最大公约数；

3. 若r≠0，则调用自身的函数gcd(n,m mod n)。

应用欧几里得算法，对于28和14，有gcd(28,14)=gcd(14,28 mod 14)=gcd(14,0)=14，验证正确。