1101 - 求两个正整数ｍ，ｎ的最大公约数

求任意两个自然数m和n的最大公约数

12 20

4

方法一：求任意两个自然数m和n的最大公约数，可以想到其最大的可能就是两个数中的较小者min，最小可能是1。所以，可以设最大公约数gcd从min开始进行判断，若gcd>1并且没有同时整除m和n，那么就gcd-1，重复判断是否整除。 方法二：求两个整数的最大公约数可以采用辗转相除法即欧几里德算法。对于任意两个自然数m和n，用m，n，r分别表示被除数、除数、余数，那么m和n的最大公约数等于n和r的最大公约数。以下是辗转相除法的算法： 1)求m除以n的余数r； 2)当r!=0,执行第3)步；若r==0，则n为最大公约数,算法结束。 3)将n的值赋给m，将r的值赋给n；再求m除以n的余数r。 4)转到第2)步