第 33 课：因数、公约数和公倍数

因数、公约数和公倍数的知识在数学及实际生活中有着广泛的应用。比如在数学领域，因数可用于分解质因数，帮助研究数的整除性等性质；在设计建筑尺寸方面，如用正方形瓷砖铺长方形地面时，瓷砖边长需为地面长和宽的公约数，以实现合理的铺设；在制订生产计划时，找出产品各部件生产周期的最小公倍数有助于安排整体生产流程。

具体什么是因数、公约数和公倍数呢？我们先来看一下蛙蛙班级的小故事。

场景引入

班主任将学生分成了若干组，准备玩一个叫作接力猜数的游戏。班主任先给出了一个数，假设这个数是 6，先让第一组的学生说出 6 能被哪些数整除，说出一个即可，比如 3。然后，班主任让第二组的学生根据前面一组说的数，说出另一个能够被这个数整除的数，比如 9。

游戏来到了第一组，班主任给的数就是 6，第一组需要回答的是 1、2、3、6 中的一个，因为这些数都能够整除 6。假设此时第一组回答的就是 3。

现在游戏来到了第二组，第二组需要回答一个能够被 3 整除的数，能被 3 整除的数实际上就是 3 的倍数，去掉 3 和 6，有 9、12、15……假设此时第二组回答的是 9。

然后来到了第三组，班主任要求第三组回答一个既是班主任给出的数 6 的倍数，又是第二组回答的数 9 的倍数的数。第三组给出的答案是 18，即 18 是 6 的倍数也是 9 的倍数。

第一组回答的数，就被称为 6 的因数；在第二组中，3 为 9 和 6 的公约数；第三组回答的 18 是 6 和 9 的公倍数。

33.1 因数及其相关知识

因数的概念

因数又称为约数。如果某个整数 a 除以某个整数 b 得到一个整数 c（其中 b ≠ 0）且没有余数，我们就说 b 是 a 的因数，例如上面 6 / 3 等于 2 没有余数，则 3 是 6 的因数。

试想一下，如果 a / b = c 且没有余数，那么能不能满足 a / c = b 且没有余数呢？比如 6 除以 3 没有余数，反过来 6 除以 2 也没有余数，所以可以看出如果 b 是 a 的因数，那么 c 也是 a 的因数。即因数大部分是成对出现的。

为什么说大部分呢？因为可能会出现 a 除以 b 得到 b 的情况，比如 16 / 4 = 4。

因数的求法

如果随便给你一个数 n，怎么知道这个数有哪些因数呢？

我们可以利用因数的特点，让一个正整数 n 除以某个小于或等于它的整数 a，如果能整除，那么 a 就是 n 的因数。

在编程中利用枚举的方法，从 1 开始枚举到 n 进行判断，如果能整除 n，那么这个数就是 n 的因数，把所有可能的数都列举一下进行判断即可。

例 1：找因数

任给一个正整数 n，求这个数的不同的因数及其个数。

如 n = 6 时，输出 1、2、3、6 四个因数，并且换行输出总数。

【输入格式】输入一行，一个不超过 10000 的正整数 n。

【输出格式】输出两行。

第 1 行输出正整数 n 的所有因数，从小到大输出，以空格隔开。

第 2 行输出因数的个数。

【输入样例】6

【输出样例】

1 2 3 6
4

解析

1. 使用 for 循环遍历从 1 到 n 的所有整数。

2. 判断计数器 i 是不是 n 的因数。通过取模运算 n % i 来判断，如果余数为 0，则说明 i 能整除 n，即 i 是 n 的因数。如果 i 是因数，将其输出。

3. 每找到一个因数，因数个数就加 1，最后输出总数。

参考代码

#include <iostream>
using namespace std;
int main()
{
    int n, s = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        if (n % i == 0)
        {
            cout << i << ' ';
            s++;
        }
    }
    cout << endl << s;
    return 0;
}

33.2 最大公约数

最大公约数的概念

最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个，举个例子，比如：

4 的因数有 1、2、4；

8 的因数有 1、2、4、8。

那么 4 和 8 共同的约数/因数中最大的那一个为 4。a 和 b 的最大公约数，记作 (a, b)。

求最大公约数，同样可以使用枚举法，先用最大的因数去除，看这两个数是否都能被这个因数整除，如果不能则继续遍历下一个因数，如果能，那么这个因数就是这两个数的最大公约数。

实现步骤

设要求的两个正整数为 a 和 b，使用枚举法求它们的最大公约数。

1. 确定较小的数：比较 a 和 b 的大小，找出其中较小的数，记为 minn。因为最大公约数不可能大于这两个数中的任何一个，所以只需从 minn 到 1 进行枚举。

2. 枚举因数：从 minn 开始，依次检查每个数是否同时是 a 和 b 的因数。如果一个数 i 满足 a % i == 0 且 b % i == 0，则说明 i 是 a 和 b 的公共因数，第一个出现的即为最大公约数。

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a, b, res, minn;
    cin >> a >> b;
    minn = min(a, b); // 求 a 和 b 的较小值
    for (int i = minn; i >= 1; i--) // 从较小值遍历到 1
    {
        if ((a % i == 0) && (b % i == 0)) // 若满足 i 为两个数的公约数
        {
            cout << i; // 输出的第一个满足条件的 i 为最大公约数
            return 0;
        }
    }
}

最大公约数的性质

1. 对于任意几个数，如果这几个数同时成倍放大，它们的最大公约数也放大相同倍数。例如，3 和 6 的最大公约数是 3，如果把它们都放大 3 倍，即变成 9 和 18，它们的最大公约数为 3 × 3 = 9，即它们的最大公约数也放大了 3 倍。

2. 对于任意整数 x，(a₁, a₂) = (a₁, a₂ + a₁ × x)，即一个整数加上另一个整数的任意倍数，它们的最大公约数不变。例如 9 和 24：

   (9, 24) = (9, 24 − 9) = (9, 15) = (9, 15 − 9) = (9, 6) = (9 − 6, 6) = (3, 6) = (3, 6 − 3) = (3, 3) = (3 − 3, 3) = (0, 3) = 3。

   注：(a, 0) = (0, a) = a。

3. 计算多元最大公约数，比如 (12, 18, 21)，可以先求出 (12, 18) = 6，再把 6 代入，求出 (6, 21) = 3，可以将这个规律称为最大公约数的结合律。

33.3 辗转相除法

辗转相除法又称欧几里得算法，是求解最大公约数的一种方法。

它的具体做法是：用较大数 m 除以较小数 n，得到的余数 r 作为下次运算中的较小数 n，原来的 n 作为下次运算中的较大数 m；如此反复，直到最后余数是 0 为止，最后的除数就是这两个数的最大公约数。下面我们通过一个例子去实现这一步骤。

例 2：辗转相除法求最大公约数

对于给定的任意两个正整数 a 和 b，求它们的最大公约数。

【输入格式】输入一行，两个正整数 a 和 b，a 和 b 均不超过 10000。

【输出格式】输出一行，一个正整数，为 a 和 b 的最大公约数。

【输入样例】6 14

【输出样例】2

【提示】本题使用辗转相除法去求解。

参考代码

#include <iostream>
using namespace std;
int main()
{
    int a, b, t;
    cin >> a >> b;
    // 辗转相除法
    while (a % b) // 余数是 0 时，终止循环
    {
        t = a % b; // 余数保存下来
        a = b;
        b = t;
    }
    cout << b;
    return 0;
}

解释：若 a 和 b 分别是 21 和 12，则第一次循环结束后 a 为 12、b 为 9；第二次循环结束后 a 为 9、b 为 3；第三次循环条件为 9 % 3 结果为 0，结束循环，输出此时的 b，即 21 和 12 的最大公约数为 3。

33.4 最小公倍数

两个或多个整数公有的倍数叫作它们的公倍数，其中除了 0 以外最小的一个公倍数就叫作这几个整数的最小公倍数，比如对于整数 4 和整数 8：

4 的倍数有 4, 8, 12, …

8 的倍数有 8, 16, 32, …

则 4 和 8 的最小公倍数为 8。a 和 b 的最小公倍数，记为 [a, b]。求最小公倍数还是可以利用枚举的思想，从小到大遍历较大的数 a 的倍数，然后判断是不是另外一个数 b 的倍数，如果是，那么遍历到的这个数就是 a 和 b 的最小公倍数。

实现步骤

1. 确定较大数：比较 a 和 b 的大小，找出其中较大的数，记为 maxn。因为最小公倍数一定大于或等于这两个数中的较大数，所以从 maxn 开始枚举。

2. 枚举寻找最小公倍数：从 maxn 开始，依次检查每个数是否能同时被 a 和 b 整除。如果一个数 i 满足 i % a == 0 且 i % b == 0，则说明 i 是 a 和 b 的公倍数，且由于是从较小的数开始枚举，所以这个 i 就是它们的最小公倍数。

参考代码

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int a, b, maxn;
    cin >> a >> b;
    maxn = max(a, b);
    for (int i = maxn; ; i++)
    {
        if (i % a == 0 && i % b == 0)
        {
            cout << i;
            return 0;
        }
    }
}

最小公倍数的性质

1. 对于任意几个数，若这几个数同时成倍放大，它们的最小公倍数也放大相同倍数。

   例如：3 和 9 的最小公倍数是 9，如果把这两个数都放大 3 倍，即 9 和 27，它们的最小公倍数为 27，即它们的最小公倍数也放大了 3 倍。

2. 计算多元最小公倍数，比如 [3, 6, 9]，可先求出 [3, 6] = 6，再把 6 代入，求出 [6, 9] = 18，这个规律被称为最小公倍数的结合律。

3. 两个数的最大公约数乘这两个数的最小公倍数等于原来两个数的乘积，比如 (16, 10) × [16, 10] = 80 × 2 = 160 = 16 × 10。

方法优化

由于两个数的乘积等于这两个数的最大公约数（用 x 表示）与最小公倍数（用 y 表示）的积，即 m × n == x × y，可以利用最大公约数求两个数字 m 和 n 的最小公倍数，实现步骤如下。

1. 求两个数字的最大公约数，设为 x。

2. m / x × n 得到 m 和 n 的最小公倍数。

接下来通过一个案例进行代码解析。