整数分解与筛法

整数分解与筛法

整数分解把一个整数还原为若干个素数幂的乘积；
筛法则在一个整数区间内批量找出这些最基本的组成单位。

1 整数的乘法结构

正整数的乘法结构可以沿着以下主线展开：

本章主线：整除 → 质数与合数 → 算术基本定理 → 因数结构 → 单个整数的判定与分解 → 区间内质数的批量筛选。

这些内容是数论函数、积性函数、模数分解和大整数分解的共同基础。

2 整除、因数与倍数

2.1 整除

设 a,b∈Za,b\in\mathbb Z 且 a≠0a\ne 0。若存在整数 kk，使得 b=akb=ak，则称 aa 整除 bb，记作 a∣ba\mid b。

此时：aa 是 bb 的因数，bb 是 aa 的倍数，若不存在这样的整数 kk，则记作 a∤ba\nmid b。

对正整数 nn 来说，11 和 nn 称为平凡因数，除此以外的因数称为非平凡因数。

整除最常用的性质是：

  • 若 a∣ba\mid b 且 b∣cb\mid c，则 a∣ca\mid c；
  • 若 a∣ba\mid b 且 a∣ca\mid c，则对任意 x,y∈Zx,y\in\mathbb Z，都有 a∣bx+cya\mid bx+cy。
与离散结构的联系

在正整数集合上定义 a⪯b⟺a∣ba\preceq b\Longleftrightarrow a\mid b，可以得到一个偏序关系。
在这个偏序下，gcd⁡(a,b)\gcd(a,b) 是最大下界，lcm⁡(a,b)\operatorname{lcm}(a,b) 是最小上界。

参见：02_关系

2.2 质数与合数

大于 11 的正整数 pp 如果只有 11 和 pp 两个正因数，则称 pp 为质数。

大于 11 且不是质数的正整数称为合数。

特别地，00 和 11 既不是质数，也不是合数；22 是唯一的偶质数。

质数由于无法继续分解，因此可以视为正整数乘法中的基本组成单位。

2.3 最大公因数与最小公倍数

正整数 a,ba,b 的所有公因数中最大的一个称为最大公因数，记作 gcd⁡(a,b)\gcd(a,b)；

所有公倍数中最小的正数称为最小公倍数，记作 lcm⁡(a,b)\operatorname{lcm}(a,b)。

它们满足：gcd⁡(a,b)lcm⁡(a,b)=ab\gcd(a,b)\operatorname{lcm}(a,b) = ab

这一恒等式将在算术基本定理之后得到更直观的解释。

3 算术基本定理

3.1 唯一质因数分解

算术基本定理：任意大于 11 的正整数 nn 都可以唯一地写成若干质数幂的乘积：

n=p1a1p2a2⋯pkak=∏i=1kpiain = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} = \prod_{i=1}^{k} p_i^{a_i}

其中 p1<p2<⋯<pkp_1<p_2<\cdots<p_k 均为质数，aia_i 均为正整数，同时这个表示称为 nn 的标准质因数分解。

3.2 因数的标准形式

设 n=∏i=1kpiai\displaystyle n=\prod_{i=1}^{k}p_i^{a_i}，正整数 dd 是 nn 的因数，当且仅当 d=∏i=1kpibi,0≤bi≤ai\displaystyle d=\prod_{i=1}^{k}p_i^{b_i}, \quad 0\le b_i\le a_i。

也就是说，构造 nn 的一个因数，只需要对每个质因数 pip_i 独立选择指数 bib_i。

3.3 因数个数

对每个 pip_i，指数 bib_i 有 0,1,…,ai0,1,\ldots,a_i 共 ai+1a_i+1 种选择。

根据乘法原理，nn 的正因数个数为 d(n)=∏i=1k(ai+1)\displaystyle d(n) = \prod_{i=1}^{k}(a_i+1)

这里也常使用记号 τ(n)\tau(n) 表示因数个数。

3.4 因数和

枚举所有指数选择并展开乘积，可以得到

σ(n)=∏i=1k(1+pi+pi2+⋯+piai)=∏i=1kpiai+1−1pi−1.\begin{aligned} \sigma(n) &=\prod_{i=1}^{k}\left(1+p_i+p_i^2+\cdots+p_i^{a_i}\right)\\ &=\prod_{i=1}^{k}\frac{p_i^{a_i+1}-1}{p_i-1}. \end{aligned}

化简采用了等比数列求和的式子。

3.5 最大公因数与最小公倍数

若 a=∏ppαp,b=∏ppβp\displaystyle a=\prod_p p^{\alpha_p}, \quad b=\prod_p p^{\beta_p}，其中没有出现的质因数视为指数 00。

则 gcd⁡(a,b)=∏ppmin⁡(αp,βp)\displaystyle \gcd(a,b)=\prod_p p^{\min(\alpha_p,\beta_p)}，lcm⁡(a,b)=∏ppmax⁡(αp,βp)\operatorname{lcm}(a,b)=\prod_p p^{\max(\alpha_p,\beta_p)}。

因为对任意非负整数 α,β\alpha,\beta 都有 min⁡(α,β)+max⁡(α,β)=α+β\min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta，

所以就可以得到 gcd⁡(a,b)lcm⁡(a,b)=ab\gcd(a,b)\operatorname{lcm}(a,b)=ab。

4 试除法

试除法适合处理单个或少量整数。

4.1 为什么只枚举到平方根

若合数 n=abn = ab，那么 a,ba, b 不可能都大于 n\sqrt{n}，否则会有 ab>nab > n。

因此，一个合数一定存在不超过 n\sqrt n 的非平凡因数。

由此得到：nn 是质数，当且仅当 22 到 ⌊n⌋\lfloor\sqrt n\rfloor 中没有整数整除 nn。

4.2 试除法判定质数

时间复杂度为 O(n)O(\sqrt n)，额外空间复杂度为 O(1)O(1)。

1
2
3
4
5
6
7
// 试除法判定素数
bool is_prime( ll n ) {
    if( n <= 1 ) return false;
    for( ll i = 2; i * i <= n; ++ i )
        if( n % i == 0 ) return false;
    return true;
}

循环条件写成 i <= n / i，可以避免 i * i 在整数范围边界附近溢出。

4.3 试除法分解质因数

发现质因数 pp 后，应连续除去所有的 pp，同时记录其指数。

1
2
3
4
5
6
7
8
9
10
11
12
13
// 试除法分解质因数
vector< pair<ll, int> > divide( ll n ) {
    vector< pair<ll, int> > res;
    for( ll i = 2; i * i <= n; ++ i ) {
        if( n % i == 0 ) {
            int cnt = 0;
            while( n % i == 0 ) n /= i, ++ cnt;
            res.push_back( { i, cnt } );
        }
    }
    if( n > 1 ) res.push_back( { n, 1 } );
    return res;
}

循环结束后若仍有 n>1n>1，则这个剩余部分一定是质数。

试除法的可用范围取决于测试组数、时限和数据分布。对接近 long long 上限的整数，通常需要 Miller–Rabin 与 Pollard–Rho，参见 08_大整数质因数分解。

5 埃拉托斯特尼筛

当需要处理 11 到 NN 范围内的全部质数时，逐个使用试除法会产生约 O(NN)O(N\sqrt N) 的复杂度。

埃氏筛通过批量标记质数的倍数来筛去合数。

5.1 核心思想

若 pp 是质数，则 2p,3p,4p,…2p,3p,4p,\ldots 都是合数。

从小到大枚举整数 ii：

  1. 若 ii 尚未被标记，则 ii 是质数；
  2. 将 ii 的倍数标记为合数。

标记可以从 i2i^2 开始，因为 2i,3i,…,(i−1)i2i,3i,\ldots,(i-1)i 都含有一个小于 ii 的因数，已经在之前被处理过。

5.2 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int maxn = 1e7 + 5;

// 埃氏筛：预处理 1...N 内的全部质数
int pri[maxn / 10], pcnt;
bool isp[maxn];

void sieve( int N ) {
    pcnt = 0;
    fill( isp + 2, isp + N + 1, true );

    for( ll i = 2; i <= N; ++ i ) {
        if( !isp[i] ) continue;
        pri[++ pcnt] = i;

        for( ll j = i * i; j <= N; j += i ) {
            isp[j] = false;
        }
    }
}

埃氏筛的时间复杂度为 O(Nlog⁡log⁡N)O(N\log\log N)，空间复杂度为 O(N)O(N)。

一个合数可能被不同质数重复标记，例如 3030 会分别作为 2,3,52,3,5 的倍数被访问。

但埃氏筛的复杂度已经非常接近线性，且实现简单、常数较小。

6 线性筛

线性筛也称欧拉筛。它进一步要求：每个合数只由其最小质因数筛去一次。

因此其时间复杂度为严格的 O(N)O(N)。

6.1 为什么遇到整除就停止

从小到大枚举 ii，再枚举已经得到的质数 pp，生成合数 i⋅pi\cdot p。

当 p∣ip\mid i 时，当前的 pp 已经是 ii 的最小质因数。

对下一个更大的质数 q>pq>p，合数 iqiq 仍然含有前一个更小的质因数 pp，所以它应该由 pp 筛去。

因此代码在 i % p == 0 后必须 break，从而实现优化。

6.2 维护最小质因数

下面的实现同时维护每个整数的最小质因数 minp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int maxn = 1e7 + 5;

// 线性筛：预处理 1..N 内的全部质数
int pri[maxn / 10], pcnt;
bool isp[maxn];

void sieve( int N ) {
    pcnt = 0;
    fill( isp + 2, isp + N + 1, true );

    for( ll i = 2; i <= N; ++ i ) {
        if( isp[i] ) pri[++ pcnt] = i;

        for( int j = 1; j <= pcnt && i * pri[j] <= N; ++ j ) {
            int p = pri[j];
            isp[i * p] = false;
            if( i % p == 0 ) break;
        }
    }
}

这里的条件 p == minp[i] 与 i % p == 0 等价，使用 minp 更直观一点。

6.3 利用最小质因数快速分解

完成 11 到 NN 的预处理后，可以沿着最小质因数不断除去当前整数：

1
2
3
4
5
6
7
8
9
10
11
// 试除法分解质因数
vector< pair<ll, int> > factorize( ll n ) {
    vector< pair<ll, int> > res;
    while( n > 1 ) {
	    int p = minp[n];
	    int exp = 0;
	    while( n % p == 0 ) n /= p, ++ exp;
	    res.push_back({ p, exp });
    }
    return res;
}

每次至少除去一个质因数，因此单次分解的循环次数不超过 O(log⁡n)O(\log n)。

7 与后续内容的联系

  • 质因数指数决定因数个数与因数和；
  • 积性函数通常由质数幂上的取值决定；
  • 线性筛可以继续递推欧拉函数、莫比乌斯函数等；
  • 模数的质因数分解是 CRT、ExLucas 等方法的重要前置；
  • 64 位大整数分解将在 Miller–Rabin 与 Pollard–Rho 中继续展开。

相关内容：

数学 > 数论
#数论/质数
整数分解与筛法
http://miqiu.space/posts/5975d5a5/
作者
Miqiu
发布于
2026年7月1日
许可协议