Question

求m和n的最大公约数，算法问题

为什么这样就可以算出最大公约数？

Answer 1

这个算法的名字叫做“辗转相除法”。
它是基于下面的性质：
1）若m是n的整数倍，则m和n的最大公约数就是n。
2）否则，若m除以n的余数是r（r<>0），则m和n的最大公约数就是n和r的最大公约数。

追问

为什么就成了n和r的最大公约数了啊？

追答

这个问题的证明，需要数论的知识，你可以自己举几个例子验证一下，认可它是正确的即可。