高效计算最大公约数 (GCD) 的算法详解

本文将介绍一种计算两个非负整数的最大公约数 (GCD) 的算法。该算法基于以下原则：

1. 如果 m 等于 0，返回 n。
2. 如果 n 等于 0，返回 m。
3. 如果 m 和 n 都是偶数，gcd(m, n) = 2 * gcd(m / 2, n / 2)。
4. 如果 m 是偶数，n 是奇数，gcd(m, n) = gcd(m / 2, n)。
5. 如果 n 是偶数，m 是奇数，gcd(m, n) = gcd(m, n / 2)。
6. 如果 m 和 n 都是奇数，gcd(m, n) = gcd((m - n) / 2, n) （或者 gcd(m, (n - m) / 2)）。

该算法可以递归实现，直到 m 和 n 相等时返回 m 或 n。

例如，计算 gcd(12, 18)：

• 12 和 18 都是偶数，所以 gcd(12, 18) = 2 * gcd(6, 9)。
• 6 是偶数，9 是奇数，所以 gcd(6, 9) = gcd(3, 9)。
• 3 是奇数，9 是奇数，所以 gcd(3, 9) = gcd((9 - 3) / 2, 3) = gcd(3, 3)。
• 3 和 3 相等，所以 gcd(3, 3) = 3。

因此，gcd(12, 18) = 2 * 3 = 6。

该算法也称为欧几里得算法，它是一种经典的算法，在计算机科学和数学中都有广泛的应用。