最大公因数（GCD）和最小公倍数（LCM）是数论中最基础的两个概念，很多算法题都会用到。本文先理清定义，再给出基于辗转相除法的 C++ 实现。

一、基本概念

因数

能整除某个整数的整数，称为这个整数的因数。例如 6 的因数有 1、2、3、6。

公因数

如果一个整数同时是几个整数的因数，就称它为这几个整数的公因数；其中最大的一个就是最大公因数（greatest common divisor，GCD）。

公倍数

在两个或两个以上的自然数中，如果它们有相同的倍数，这些倍数就是它们的公倍数；其中最小的一个就是最小公倍数（lowest common multiple，LCM）。

二、热身：几组数

a b 最大公因数 gcd 最小公倍数 lcm
12 18 6 36
15 25 5 75

可以先自己想一想：6 和 36、5 和 75 是怎么来的？

三、最大公因数 GCD

英文三个单词正好对应它的含义：

  • greatest：最大的
  • common：共同的
  • divisor：因数

辗转相除法（欧几里得算法）

这是求 GCD 最经典的方法：不断用较大数除以较小数，把「除数」和「余数」作为新的一对数继续相除，直到余数为 0，此时的除数就是最大公因数。

步骤如下：

  1. 用大数除以小数，得到余数；
  2. 把上一步的除数当被除数、余数当除数，重复相除；
  3. 当余数为 0 时，当前的除数就是最大公因数。

以计算 48 和 18 的 GCD 为例：

1
2
3
48 ÷ 18 = 2 …… 12
18 ÷ 12 = 1 …… 6
12 ÷ 6  = 2 …… 0   ← 余数为 0，故最大公因数是 6

递归写法的 C++ 实现：

1
2
3
4
int gcd(int a, int b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
1
2
3
int gcd(int a, int b){
	return b?gcd(b,a%b):a;
}

递归到 b == 0 时直接返回 a，对应上面「余数为 0，除数即为答案」的最后一步。C++17 起标准库也提供了 std::gcd（在 <numeric> 头文件中），但手写一版更有助于理解。

四、最小公倍数 LCM

  • lowest：最小的
  • common：共同的
  • multiple：倍数

还是以 48 和 18 为例：48 × 3 = 144，18 × 8 = 144，所以它们的最小公倍数是 144。

但靠枚举试出来太慢。只要知道了两个数的最大公因数，就能用一条公式直接求出最小公倍数：

lcm(a, b) = a × b ÷ gcd(a, b)

C++ 实现：

1
2
3
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}

注意代码里是先除后乘，而不是直接写 a * b / gcd(a,b)：因为 a * b 可能先超出 int 范围导致溢出，而 a 一定能被 gcd(a,b) 整除，先除不会丢精度。

五、完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;

int gcd(int a, int b) {  // 最大公因数
	if (b == 0) return a;
	return gcd(b, a % b);
}

int lcm(int a, int b) {  // 最小公倍数
	return a / gcd(a, b) * b;
}

int main() {
	int a, b;
	cin >> a >> b;
	cout << "最大公因数：" << gcd(a, b) << "\n最小公倍数：" << lcm(a, b);
	return 0;
}

六、小结

  • GCD 用辗转相除法：gcd(a, b) = gcd(b, a % b)，余数为 0 时结束；
  • LCM 靠 GCD 算：lcm(a, b) = a × b ÷ gcd(a, b)；
  • 工程实现中先除后乘，避免乘积溢出；
  • ⚠️ 数据范围大时（比如乘积可能超过 21 亿），把参数和返回值都改成 long long。