公约数与公倍数

一、先认识因数和倍数

如果 a 除以 b 没有余数，也就是 a % b == 0，那么 b 是 a 的因数，同时 a 是 b 的倍数。

二、最大公因数

例子：18 和 24

三、辗转相除法

重要规律：两个数 m 和 n 的最大公因数，等于 n 和余数 r 的最大公因数。

1. 1
   计算 r = m % n，得到余数。
2. 2
   如果余数不是 0，就让 m = n、n = r。
3. 3
   继续计算新的余数。余数变成 0 时，n 就是答案。

用辗转相除法计算 24 和 18

C++ 模板

int m, n;
cin >> m >> n;

int r = m % n;
while (r != 0) {
    m = n;
    n = r;
    r = m % n;
}

cout << n;

四、最小公倍数

例子：18 和 24

五、用公式求最小公倍数

18 × 24 ÷ 6 = 72

同时求最大公因数和最小公倍数

#include <iostream>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;

    int m = a;
    int n = b;
    int r = m % n;
    while (r != 0) {
        m = n;
        n = r;
        r = m % n;
    }

    int gcd = n;            // 最大公因数
    int lcm = a / gcd * b;  // 最小公倍数

    cout << "最大公因数：" << gcd << endl;
    cout << "最小公倍数：" << lcm << endl;
    return 0;
}

六、容易混淆的地方

• 因数通常比较小：它可以整除原来的数。
• 倍数通常不断变大：一个正整数的倍数有无数个。
• 最大公因数找“最大的共同因数”：答案不会大于两个数中较小的数。
• 最小公倍数找“最小的共同倍数”：答案不会小于两个数中较大的数。
• 公式法要先正确求出最大公因数，并保存原来的两个数。
• 本页程序讨论的是两个正整数，输入的两个数都应大于 0。

七、动手练习