一、什么是公约数
公约数，也称为公因数，是指两个或多个整数共有的因数。具体来说，如果一个整数能被两个或多个整数整除，那么这个整数就是这些整数的公约数。
例如，考虑整数 12 和 18：
- 12 的因数有：1, 2, 3, 4, 6, 12
- 18 的因数有：1, 2, 3, 6, 9, 18
12 和 18 的公约数是它们共有的因数，即：1, 2, 3, 6
补充：最小公倍数 (LCM)
定理： a、b 两个数的最小公倍数 (lcm) 乘以它们的最大公约数 (gcd) 等于 a 和 b 本身的乘积。
如：gcd(a,b) * lcm(a,b) = a*b
所以，只要学会 gcd，lcm 就能直接推导出来：
lcm(a,b) = a*b/gcd(a,b)
二、计算最大公约数的方法
学习数论的一系列算法时，往往直接看算法是看不懂的。这里我们先学习数学解法，再给出算法。
1. 辗转相除法（欧几里得算法）
数学原理
假设我们有两个正整数 a 和 b，其中 a > b。根据辗转相除法，最大公约数 gcd(a,b) 可以通过以下步骤求得：
- 第一步：计算 a mod b，得到余数 r。
- 第二步：将 a 替换为 b，将 b 替换为 r。
- 第三步：重复上述步骤，直到 b=0 时，此时 a 即为最大公约数。
下方用 (18, 12) 举例。
代码实现
基础版本：
#include <iostream>
using namespace std;
// 求公约数
int gcd(int a, int b) {
while (a % b != 0) {
int c = a % b;
a = b;
b = c;
}
return b;
}
int main() {
int a = 18, b = 12;
cout << gcd(a, b) << endl;
return 0;
}
详细注释版：
