最大公因数与最小公倍数

✅ 什么是欧几里得算法（辗转相除法）？

一句话：

就是不断用“大数 ÷ 小数”，然后把“小数”与“余数”继续来除，直到余数变成 0，那个最后的除数就是最大公因数。

✅ 为什么这么做是对的？（傻瓜理解逻辑）

假设你要找两个数的最大公因数，比如 18 和 12。

你可能第一想法：

“我把它们俩共同的因数列出来比较一下？”

18 的因数：1 2 3 6 9 18
12 的因数：1 2 3 4 6 12
共同的：1 2 3 6
最大：6

对！结果是6。

但欧几里得算法的做法是：

✅ 按步骤傻瓜化演示（以 18 和 12 为例）

步骤 操作 说明
1 18 ÷ 12 = 商 1 余 6 原来18和12的“共同因数”能帮我产生这个 6
2 接下来把“12”和“6”继续做除法 也就是 12 ÷ 6
3 12 ÷ 6 = 商 2 余 0 余数为0说明整除了
4 最后一次 被除数 就是最大公因数 6 就是最大公因数

记住一句核心口诀：

大数 ÷ 小数 = 余数
再用小数 ÷ 余数
循环到余数是0为止
最后的除数 = 最大公因数

✅ 再举一个（稍微难一点）

求 144 和 60 的最大公因数：

步骤 计算 余数 继续
1 144 ÷ 60 24 再用 60 ÷ 24
2 60 ÷ 24 12 再用 24 ÷ 12
3 24 ÷ 12 0 余数为0
结束 最大公因数 = 12

所以 gcd(144, 60) = 12

✅ 为什么“余数”还能继续当“测量尺”？

可以这样理解：

你是在找一个能把两个数都整除的“最大尺子”。
第一次除法把“大尺子测不准的部分”（多出来的）变成了“余数”，
后面继续用“更精准的尺子”（余数）去替代原本的小的那个数。

不断“削小尺子”，直到它完全贴合。
贴合时就是最大公因数。

✅ 用一句最通俗的话总结

不断用更小的尺子去量两个数，直到刚好不剩丁点，这个尺子就是最大公因数

[!NOTE]

公式:gcd(a, b) = gcd(b, a % b)

最小公倍数求法

✅ 但是列倍数太慢，所以有了一个超级快的公式

数学上有个结论（可靠且可以证明）：

两个数的乘积 = 最大公因数 × 最小公倍数

所以推出来：

最小公倍数 = (a × b) ÷ 最大公因数

这个公式就是最常用的方法。

✅ 举个例子

求 12 和 18 的最小公倍数

  1. 先求最大公因数
    gcd(12, 18) = 6 （辗转相除法能算出来）
  2. 用公式
    lcm = (12 × 18) ÷ 6
    = 216 ÷ 6
    = 36

所以 最小公倍数 = 36

✅ 为什么乘积除以 gcd 就对了？（傻瓜解释）

因为：

项目 理解方式
乘积 把两个数的所有因子都堆上去了（重复了一部分）
gcd 是那部分“重复”的公共身份
除 gcd 就把“重复部分”扣掉，只剩下最刚好的倍数

✅ 最通俗一句话

最小公倍数就是：两个数的乘积，把重复分母（最大公因数）扣掉后的结果。

如果你现在理解了原理，下一步我可以给你写最小公倍数的 C 语言代码，并且逐行教你怎么写、为什么这么写。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*
 * 题目绍介:
就是说输入两个数 然后生成最大公因数和最小公倍数罢了 很简单只是拿来当例子
 */
#include <stdio.h>
//快读
int fastRead() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * f;
}
//快写
void fastWrite(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9)
        fastWrite(x / 10);
    putchar(x % 10 + '0');
}
int gcd(int m,int n) {return m%n==0?n:gcd(n,m%n);}//这个就是那个最大公因数 用了递归
int lcm(int m,int n,int gcd) {return (n*m)/gcd;}//最小公倍数的公式
int main() {
    int m=fastRead(),n=fastRead();
    int res = gcd(m,n);
    fastWrite(res);
    putchar('\n');
    fastWrite(lcm(m,n,res));
}