质因子分解

唯一分解定理¶

对于任意一个大于 $1$ 的正整数 $n$，都可以唯一地分解为若干个质数的乘积，形式如下：

\[ n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k},\quad p_i \in \text{prime},\ a_i \in \mathbb{Z}^+ \]

例如：

$12 = 2^2 \times 3^1$
$9 = 3^2$
$5 = 5^1$

这一性质被称为唯一分解定理，是数论中的基石。

朴素质因子分解方法¶

思路

从 $2$ 开始枚举每个整数 $i$，尝试整除 $n$。
每当 $i \mid n$，就连续除尽 $n$ 中的所有 $i$，统计次数。
枚举只需要到 $\sqrt{n}$，因为若 $n$ 有大于 $\sqrt{n}$ 的因子，另一个因子必定小于它。
最后如果 $n > 1$，说明剩下的 $n$ 本身是一个质数。

实现

for (int i = 2; i * i <= n; i++) // 注意 i * i 是否溢出 int
{
    if (n % i == 0)
    {
        int cnt = 0;
        while (n % i == 0)
        {
            n /= i;
            cnt++;
        }
        if (cnt) cout << i << " " << cnt << "\n";
    }
}
if (n != 1)
{
    cout << n << " 1\n"; // 剩余一个大质因子
}

时间复杂度：$O(\sqrt{n})$

质因子分解的应用¶

约数个数定理

若 $n = p_1^{a_1} \times p_2^{a_2} \times \cdots \times p_k^{a_k}$，则 $n$ 的正整数约数个数为：

\[ \text{d}(n) = (a_1+1)(a_2+1)\cdots(a_k+1) = \prod_{i=1}^k (a_i+1) \]

原理：每个质因子 $p_i$ 可以选 $0$ 到 $a_i$ 次，共 $a_i + 1$ 种选法，乘法原理得总数。

约数和定理

\[ \text{s}(n) = (p_1^0 + p_1^1 + \cdots + p_1^{a_1}) \times \cdots \times (p_k^0 + p_k^1 + \cdots + p_k^{a_k}) \]

等比数列求和可化简为：

\[ \text{s}(n) = \prod_{i=1}^k \frac{p_i^{a_i+1} - 1}{p_i - 1} \]

常见技巧与应用¶

最大公约数（GCD）的质因子分析

若：

$a = p_1^{x_1}\cdot p_2^{x_2}\cdot \cdots$
$b = p_1^{y_1}\cdot p_2^{y_2}\cdot \cdots$

则：

\[ \gcd(a,b) = p_1^{\min(x_1, y_1)} p_2^{\min(x_2, y_2)} \cdots \]

最小公倍数（LCM）的质因子分析

\[ \text{lcm}(a,b) = p_1^{\max(x_1, y_1)} p_2^{\max(x_2, y_2)} \cdots \]

这些方法同样适用于多个数字的 GCD / LCM 计算。

快速质因子分解¶

场景

当需要对大量不大的数进行质因子分解时，可以先筛出每个数的最小质因子 $f[i]$，再在对数时间内完成分解。

实现思路

使用欧拉筛或埃氏筛预处理每个 $i$ 的最小质因子。
对于任意 $n$，只需不断除以 $f[n]$，直到 $n = 1$，即可完成分解。

代码实现

int f[N], p[N], cnt;
bool vis[N];

void prime(int n)
{
    vis[0] = vis[1] = true;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            p[++cnt] = i;
            f[i] = i;
        }
        for (int j = 1; j <= cnt && i * p[j] <= n; j++)
        {
            vis[i * p[j]] = true;
            f[i * p[j]] = p[j];
            if (i % p[j] == 0) break;
        }
    }
}

void factorize(int n)
{
    map<int, int> cnt;
    while (n != 1)
    {
        cnt[f[n]]++;
        n /= f[n]; // 除以自己的最小质因子，快速分解
    }
    for (auto it : cnt)
        cout << it.first << "^" << it.second << " ";
    cout << "\n";
}

时间复杂度

筛预处理：$O(n)$
单次分解：$O(\log n)$

应用

适用于海量数据处理，如分解 $10^6$ 个 $\leq 10^8$ 的数。