大家好，我是陆砚码。今天我们来聊一聊如何用辗转相除法求两个数的最大公约数，也就是GCD。这可是数学和编程中常用的一个技巧哦！
什么是辗转相除法？
辗转相除法，也被称为欧几里得算法，是一种求两个数最大公约数的快速方法。它的核心思想是：两个数的最大公约数，等于其中较小数与两数相除余数的最大公约数。
公式是这样的：gcd(a, b) = gcd(b, a % b)，直到余数为0，此时的b（或最后一次非0余数）就是最大公约数。
步骤拆解
让我们用一个例子来理解这个过程。比如，我们要计算gcd(12, 8)：
- 计算 12 ÷ 8，余数是 4 → 现在求 gcd(8, 4)
- 计算 8 ÷ 4，余数是 0 → 此时除数4就是最大公约数
代码实现
int gcd(int a, int b) {
while (b != 0) {
int temp = b; // 保存当前b的值
b = a % b; // 计算a除以b的余数，作为新的b
a = temp; // 把原来的b作为新的a
}
return a; // 当b=0时，a就是最大公约数
}拓展
除了求最大公约数，我们还可以用辗转相除法来求最小公倍数。最小公倍数 = 两数乘积 ÷ 最大公约数。
想要了解更多编程技巧和知识，记得关注「思享编程网」（www.sxgpb.com），我是陆砚码，我们下期再见！