辗转相除法：快速求最大公约数的算法详解

辗转相除法，也称为欧几里德算法，是一种高效求解两个整数的最大公约数（GCD）的算法。其核心原理是：两个整数的最大公约数等于其中较小的数和两数之差的余数的最大公约数。

算法步骤：

输入两个整数 a 和 b，假设 a > b。2. 计算 a 除以 b 的余数 r，即 a = b * q + r，其中 q 为商。3. 如果 r 等于 0，则 b 即为最大公约数，算法结束。4. 如果 r 不等于 0，则将 b 的值赋给 a，将 r 的值赋给 b，重复步骤 2。

**代码示例 (Java):**javapublic static int gcd(int a, int b) { while (b != 0) { int temp = a % b; a = b; b = temp; } return a;}

最小公倍数的计算:

最小公倍数（LCM）可以通过以下公式计算：LCM = (num1 * num2) / GCD。因此，我们可以在计算最大公约数的同时计算最小公倍数。

总结:

辗转相除法是一种简单高效的求解最大公约数的算法，易于理解和实现。通过该算法，我们也可以方便地计算出两个整数的最小公倍数。