Question

求两个数的最大公约数

Answer 1

整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，就将b称为a的约数。

最大公约数指两个或多个整数共有 约数 中最大的一个。
求数值3和数值9的最大公约数。数值3的正约数有1, 3，数值9的正约数有1, 3, 9，数值3与数值9约数交集（既存在3的约数集中，又存在9的约数集中的数的集合）为1、3。则最大公约数为3。写作gcd(3, 9) = 3。

辗转相除法是以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数的计算公式。例如，求1997与615的最大公约数：
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
所以，最大公约数为1。

从上面的辗转相除法可以看出，这一轮的除数为下一轮的被除数，这一轮的余数为下一轮的除数。所以，求num1与num2的最大公约数，我们要做的就是：
首先判断num2是否为0，若为0，则返回num1（最大公约数为num1）
若不为0，则递归调用函数，把num2作为第一个参数，num1与num2的余数作为第二个参数传进去：