最大公约数（欧几里得算法）

引言

两个数的最大公约数（GCD）或最大公因数（HCF）是指能够同时整除这两个数的最大正整数。换句话说，两个整数（a, b）的最大公约数，记作 gcd(a,b)，定义为满足 d | a 且 d | b 的最大正整数 d，其中 x | y 表示 x 能整除 y。

一种简单的解法是找出两个数的所有质因数，然后找到它们共有的因数的交集，最后返回交集中所有元素的乘积。

根据欧几里得算法：

1gcd(A, B) = gcd(B, A % B) // GCD 的递推关系
2gcd(A, 0) = A // 基础情况

证明

下面我们讨论递推关系的正确性。

• 假设 a = bq + r。
• 设 d 是 a 和 b 的任意一个公因数，即 d | a 且 d | b，则可推出 d | (a – bq)，进而得到 d | r。
• 设 e 是 b 和 r 的任意一个公因数，即 e | b 且 e | r，则可推出 e | (bq + r)，即 e | a。

由此可见，a 和 b 的任意公因数也一定是 r 的因数；反之，b 和 r 的任意公因数也一定是 a 的因数。因此，d 是 a 和 b 的公因数，当且仅当 d 是 b 和 r 的公因数。

对于超过两个数的最大公约数，例如 gcd(a,b,c)，其值等于 gcd(a, gcd(b,c))，以此类推。

解法

在进入代码实现之前，先通过下方的可视化图示来理解该问题的解决思路。

现在你已经对这一方法有了基本理解，接下来我们将其转化为代码实现。

1#include <iostream>
2using namespace std;
3
4int gcd(int a, int b) {
5  return (b == 0 ? a : gcd(b, a % b));
6}
7
8int main() {
9  int a = 100, b = 20;
10  int result;
11  result = gcd(a,b);
12  cout << result;
13}

说明：

• 上述 gcd() 函数接收两个数作为输入并返回结果。由于使用了 % 运算符，递归调用次数将少于 n，其中 n = max(a,b)。
• 欧几里得求 GCD 算法的时间复杂度为 O(log(N))，其中 N = max(a,b)。