数论篇 —— 最大公约数 与 分解质因数

一、最大公约数（GCD）

1. 定义

两个正整数 a 和 b 的最大公约数，是指能同时整除 a 和 b 的最大正整数，记作 gcd(a, b)。

2. 核心性质

• 交换律：gcd(a, b) = gcd(b, a)
• 欧几里得核心公式：两个数的最大公约数，等于其中较小一个数与两数相除余数的最大公约数，即gcd(a, b) = gcd(b, a % b)
• 边界条件：gcd(a, 0) = a

3. 标准实现：欧几里得算法

迭代写法

int gcd(int a, int b) {
    while (b != 0) {
        int tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

递归写法

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

二、分解质因数

1. 定义

将一个正整数表示为若干个质数相乘的形式，这个过程叫做分解质因数。
例如：12 = 2 × 2 × 3 = 2² × 3

2. 核心原理

• 算术基本定理：任何大于1的正整数，都可以唯一分解为有限个质数的乘积
• 优化原理：任何合数 n 都至少有一个质因数 ≤ √n，因此只需枚举到 √n 即可

3. 代码实现：试除法

void factorize(int n) {
    int tmp = n;
    for (int i = 2; i * i <= n; i++) {
        if (tmp % i == 0) {
            while (tmp % i == 0) {
                cout << i << " "; // 输出质因数
                tmp /= i;
            }
        }
    }
    // 最后剩下的大于1的数也会是质数
    if (tmp > 1) {
        cout << tmp;
    }
}

三、时间复杂度总结