素数判定算法 - Colton Star Blog

Colton/曹越

公告

标签

Colton/曹越

公告

标签

Colton/曹越

公告

标签

站点统计

文章

19

分类

6

标签

34

总字数

17,478

运行天数

0 天

最后活动

0 天前

1798 字

5 分钟

素数判定算法

2026-07-05

算法

/

数学

/

数论

素数判定是 ACM 最基础的操作之一。根据数据规模不同，用错方法可能从「秒过」变「TLE 到死」。本文从试除法开始，到筛法，再到 Miller-Rabin，讲清楚每种方法能处理多大范围、什么时候用。

一、试除法#

1.1 朴素版#

从 2 到 n-1 逐个试除，找到一个因子就是合数。

1
bool is_prime(int n) {
2
    if (n < 2) return false;
3
    for (int i = 2; i < n; i++)
4
        if (n % i == 0) return false;
5
    return true;
6
}

能处理的范围： $n \le 10^6$ （勉强）

1.2 优化：只除到 √n#

若 n 是合数，必有一个因子 $\le \sqrt{n}$ 。

1
bool is_prime(int n) {
2
    if (n < 2) return false;
3
    for (int i = 2; i * i <= n; i++)   // 只到 √n
4
        if (n % i == 0) return false;
5
    return true;
6
}

能处理的范围： $n \le 10^{12}$ （约需 $10^6$ 次运算，能跑）； $n \approx 10^{18}$ 时会超时。

1.3 毫秒级优化：6k ± 1 跳跃#

所有 ≥ 5 的素数都是 $6k \pm 1$ 的形式。

1
bool is_prime(int n) {
2
    if (n < 2) return false;
3
    if (n == 2 || n == 3) return true;
4
    if (n % 2 == 0 || n % 3 == 0) return false;
5

6
    for (int i = 5; i * i <= n; i += 6) {
7
        if (n % i == 0 || n % (i + 2) == 0)
8
            return false;
9
    }
10
    return true;
11
}

跳过了 2 和 3 的倍数，减少约 $\frac{2}{3}$ 的工作量。常数优化，复杂度不变。

试除法小结#

版本	范围	备注
朴素	$n < 10^6$	别用
到 √n	$n < 10^{12}$	ACM 最常用
6k±1	$n < 10^{12}$	常数更快
不能处理	$n > 10^{14}$	换 Miller-Rabin

二、埃氏筛与欧拉线性筛#

当需要批量生成素数（1~N 全部找出来）时，筛法比反复调 is_prime() 快得多。

2.1 埃拉托斯特尼筛法（埃氏筛）#

素数的倍数一定是合数。从最小的素数开始，把它的倍数标记掉；下一个没被标记的数就是素数。

1
vector<int> eratosthenes(int n) {
2
    vector<bool> is_prime(n + 1, true);
3
    is_prime[0] = is_prime[1] = false;
4

5
    for (int i = 2; i * i <= n; i++) {
6
        if (is_prime[i]) {
7
            for (int j = i * i; j <= n; j += i) {
8
                is_prime[j] = false;
9
            }
10
        }
11
    }
12

13
    vector<int> primes;
14
    for (int i = 2; i <= n; i++)
15
        if (is_prime[i]) primes.push_back(i);
16
    return primes;
17
}

关键点：

外层只到 $\sqrt{n}$ （为什么？合数必有一个因子 $\le \sqrt{n}$ ）
内层从 $i^2$ 开始（为什么？ $2i, 3i, \dots, (i-1)i$ 早被更小的素数筛过了）

复杂度： $O(N\log\log N)$ ，实际非常接近线性。

2.2 常数优化：跳过偶数#

1
vector<int> eratosthenes_fast(int n) {
2
    vector<bool> is_prime(n + 1, true);
3
    is_prime[0] = is_prime[1] = false;
4

5
    for (int i = 4; i <= n; i += 2)
6
        is_prime[i] = false;                // 偶数全标记
7

8
    for (int i = 3; i * i <= n; i += 2) {   // 只检查奇数
9
        if (is_prime[i])
10
            for (int j = i * i; j <= n; j += 2 * i)
11
                is_prime[j] = false;
12
    }
13

14
    vector<int> primes;
15
    primes.push_back(2);
16
    for (int i = 3; i <= n; i += 2)
17
        if (is_prime[i]) primes.push_back(i);
18
    return primes;
19
}

就加几行，速度再提一个档次。

2.3 欧拉筛（线性筛）#

埃氏筛的问题：同一个合数可能被多个质因子重复标记。

1
12 会被 2 标记一次，又被 3 标记一次 → 重复

欧拉筛的核心：每个合数只被它的最小质因子（LPF）筛掉，真正 $O(N)$ 。

1
vector<int> euler_sieve(int n) {
2
    vector<bool> is_prime(n + 1, true);
3
    vector<int> primes;
4

5
    is_prime[0] = is_prime[1] = false;
6

7
    for (int i = 2; i <= n; i++) {
8
        if (is_prime[i]) primes.push_back(i);
9

10
        for (int p : primes) {
11
            if (i * p > n) break;
12
            is_prime[i * p] = false;         // 筛掉 i×p
13
            if (i % p == 0) break;           // ★ 关键
14
        }
15
    }
16
    return primes;
17
}

if (i % p == 0) break 是什么意思？

p 是从小到大枚举的已知素数
当 i % p == 0，说明 p 是 i 的最小质因子
如果继续用更大的 $p'$ 筛， $i \times p'$ 的最小质因子是 p 而不是 p’，违背了”只用最小质因子筛”的原则
所以要停，后面的留到更大的 i 去筛

额外收获：修改三行就能同时拿到每个数的最小质因子，之后 $O(\log N)$ 分解质因数：

1
vector<int> lpf(n + 1, 0);
2
// ... 在筛的时候顺手填 lpf[i * p] = p;
3
// 之后:
4
while (x > 1) {
5
    int p = lpf[x], cnt = 0;
6
    while (x % p == 0) cnt++, x /= p;
7
    // (p, cnt) 就是一个质因子及其次数
8
}

筛法对比#

	埃氏筛	欧拉筛
复杂度	$O(N\log\log N)$	$O(N)$
重复标记	有	无
额外信息	仅 is_prime	可同时拿 LPF
代码量	5 行	10 行
N=10⁷ 实测	~0.10s	~0.15s
何时用	日常刷题	需要质因数分解，或 N 极大

三、Miller-Rabin 素性测试#

当 n 超过 $10^{14}$ ，试除法跑不动了。Miller-Rabin 能在毫秒内判定 64 位范围的任意整数是否为素数。

3.1 能处理多大？#

方法	可判定范围
试除法	$n \le 10^{12}$
Miller-Rabin	$n \le 2^{64} \approx 1.8 \times 10^{19}$

3.2 模板（直接复制用）#

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4

5
int qpow(int a, int b, int mod) {
6
    int res = 1;
7
    a %= mod;
8
    while (b) {
9
        if (b & 1) res = (__int128)res * a % mod;
10
        a = (__int128)a * a % mod;
11
        b >>= 1;
12
    }
13
    return res;
14
}
15

16
bool is_prime(int n) {
17
    if (n < 2) return false;
18
    if (n == 2) return true;
19
    if (n % 2 == 0) return false;
20

21
    // 底数选择（这里用 7 个底数覆盖 64 位，放模板里不用记）
22
    int bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
23

24
    int d = n - 1, s = 0;
25
    while (d % 2 == 0) {
26
        d /= 2;
27
        s++;
28
    }
29

30
    for (int a : bases) {
31
        if (a % n == 0) continue;
32

33
        int x = qpow(a, d, n);
34
        if (x == 1 || x == n - 1) continue;
35

36
        for (int r = 1; r < s; r++) {
37
            x = (__int128)x * x % n;
38
            if (x == n - 1) break;
39
        }
40
        if (x != n - 1) return false;
41
    }
42
    return true;
43
}

3.3 底数记忆法#

ACM 中 99% 的题 n ≤ 2³²（约 4.3×10⁹），只需要记 3 个底数：

1
{2, 7, 61}

2 → 7 → 61，三个素数，连续变大。记住就行。

如果题目 n 大到 64 位，把模板里的 7 个底数写死在代码里，不用记。那一长串就是放在模板里存着的。

n 的范围	底数	需要记吗
< 2³²（常规题）	{2, 7, 61}	✅ 记住
< 2⁶⁴（极少数）	{2, 325, 9375, 28178, 450775, 9780504, 1795265022}	❌ 放模板

3.4 怎么用？三步#

1
① 复制模板代码到你开赛的 .cpp 里
2
② 调用 is_prime(n)，返回 true/false
3
③ 完了

1
cout << is_prime(998244353) << endl;   // 1
2
cout << is_prime(561) << endl;         // 0（卡迈克尔数，试除法能过但 MR 能识破）

3.5 如果编译器不支持 `__int128`#

换用手写安全乘法：

1
int mul(int a, int b, int mod) {
2
    int res = 0;
3
    a %= mod;
4
    while (b) {
5
        if (b & 1) res = (res + a) % mod;
6
        a = (a + a) % mod;
7
        b >>= 1;
8
    }
9
    return res;
10
}

然后把 qpow 里的 (__int128)x * y % n 全换成 mul(x, y, n)。

3.6 常见坑#

问题	解决
负数进来	开头 `if (n < 2) return false;`
只判单个大数	用 MR；批量筛素数用埃氏筛
`__int128` 不支持	用手写 `mul()`
n 在 32 位以内	把底数改成 `{2, 7, 61}`，少跑几轮更快

四、总览：什么时候用哪个#

1
需要批量生成素数？ ──── 是 ──→ 埃氏筛（或欧拉筛拿 LPF）
2
        │
3
        否
4
        │
5
        ↓
6
    n ≤ 10¹²？ ──── 是 ──→ 试除法（到 √n，6k±1 优化）
7
        │
8
        否
9
        │
10
        ↓
11
    n ≤ 2⁶⁴？ ──── 是 ──→ Miller-Rabin
12
        │
13
        否
14
        │
15
        ↓
16
    大数库 / Python 的 isprime()

三件武器，按数据规模选。ACMer 背包里常备这三样就够了。

五、实战案例：Primer Distance（POJ 2689）#

题目#

给定多组 $[l, r]$ ， $0 < l < r < 2^{31}$ ， $r - l \le 10^6$ 。输出区间内相邻素数差的最大值和最小值。

核心难点#

$r$ 可以到 $2^{31}$ ，直接用埃氏筛 → 内存爆炸。但 $r - l \le 10^6$ 很小——这是突破口。

两种思路#

思路一：筛 $\sqrt{r} \approx 46340$ 的素数表，再用它们去筛区间 $[l, r]$ （分段筛）。

思路二：Miller-Rabin 遍历 $[l, r]$ 每个数，逐个判定。

	分段筛	Miller-Rabin 硬扫
代码量	多几行	直接套模板
速度	筛表 O(√r)，区间 O((r-l) log log r)	最坏 ~10⁶ × 7 轮模幂
稳妥性	✅ 所有 OJ 通吃	⚠️ 常数大，可能 TLE

结论：分段筛是标准答案。

分段筛解法#

1
① 筛 [2, √r] 的素数            → 不到 5000 个素数
2
② 用这些素数标记 [l, r] 的合数  → 10⁶ 的 bool 数组
3
③ 收集区间素数，遍历找答案     → O(区间长度)

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
vector<int> get_primes(int n) {
5
    vector<bool> is_prime(n + 1, true);
6
    vector<int> primes;
7
    for (int i = 2; i <= n; i++) {
8
        if (is_prime[i]) primes.push_back(i);
9
        for (int j = 0; j < (int)primes.size() && i * primes[j] <= n; j++) {
10
            is_prime[i * primes[j]] = false;
11
            if (i % primes[j] == 0) break;
12
        }
13
    }
14
    return primes;
15
}
16

17
int main() {
18
    ios::sync_with_stdio(false);
19
    cin.tie(nullptr);
20

21
    // ① 只筛 √(2³¹) ≈ 46340
22
    auto small = get_primes(50000);
23

24
    long long l, r;
25
    while (cin >> l >> r) {
26
        // ② 用小区间标记合数
27
        vector<bool> is_prime(r - l + 1, true);
28
        for (long long p : small) {
29
            if (p * p > r) break;
30
            // 找到 p 在 [l, r] 内的第一个倍数
31
            long long start = max(p * p, (l + p - 1) / p * p);
32
            for (long long j = start; j <= r; j += p)
33
                is_prime[j - l] = false;
34
        }
35
        if (l == 1) is_prime[0] = false;  // 1 不是素数
36

37
        // ③ 收集区间内的素数
38
        vector<long long> primes;
39
        for (long long i = l; i <= r; i++)
40
            if (is_prime[i - l])
41
                primes.push_back(i);
42

43
        if (primes.size() < 2) {
44
            cout << "There are no adjacent primes.\n";
45
            continue;
46
        }
47

48
        long long mn = primes[1] - primes[0], mx = mn;
49
        long long c1 = primes[0], c2 = primes[1];  // closest
50
        long long d1 = primes[0], d2 = primes[1];  // distant
51

52
        for (int i = 1; i < (int)primes.size() - 1; i++) {
53
            long long diff = primes[i + 1] - primes[i];
54
            if (diff < mn) mn = diff, c1 = primes[i], c2 = primes[i + 1];
55
            if (diff > mx) mx = diff, d1 = primes[i], d2 = primes[i + 1];
56
        }
57

58
        printf("%lld,%lld are closest, %lld,%lld are most distant.\n",
59
               c1, c2, d1, d2);
60
    }
61
}

关键细节#

① 起始位置的写法

1
long long start = max(p * p, (l + p - 1) / p * p);

p * p：从 p² 开始，跟埃氏筛一样——更小的倍数早被更小的素数筛过了
(l + p - 1) / p * p：如果 $p^2 < l$ ，需要找到 p 在区间内的第一个倍数。(l + p - 1) / p 是向上取整除法

1
例：l=100, p=7
2
    (100 + 7 - 1) / 7 * 7 = 106 / 7 * 7 = 15 * 7 = 105
3
    105 是 ≥100 的第一个 7 的倍数 ✓

② 为什么筛到 50000 而不是 46340？

46340 是 $\sqrt{2^{31}}$ 的精确值，取 50000 多筛一点不碍事，写代码方便。

③ 数组偏移 j - l

1
is_prime[j - l] = false;

区间起始是 l，不是 1。用 j - l 映射到数组下标。数组大小 r - l + 1。

你的代码回顾#

回到你之前的那段代码，问题在于：

你的写法	问题
`n = pow(2, 30)`	筛了 10 亿个，~560MB 内存，必爆 MLE
`is_prime[0],[1]` 未置 false	0 和 1 会被当成素数
`it2 = upper_bound(u) - 1` 直接用	没有先判断区间里有没有素数，可能越界
`maxn = -1` / `minn = 999...`	魔法数字，不优雅

思路没方向性错误，只是筛的范围搞错了——不该筛整个 [0, 2^30]，只筛 √r，然后分段筛区间，正是这题的核心技巧。

六、阶乘分解（P10495）#

题目#

给定 $N \le 10^6$ ，将 $N!$ 分解质因数，按算术基本定理输出每个质因子及其次数。

1
输入：5
2
输出：2 3      （5! = 2³ × 3¹ × 5¹）
3
      3 1
4
      5 1

思路对比#

	朴素：分解每个数	勒让德公式
做法	遍历 2→N，每个数质因数分解，累加到桶	对每个素数 p，直接算它在 N! 中的总次数
运算量	O(N log N)，常数大	约 N 个素数 × log_p(N) 次除法
需要桶	需要	不需要，算一个输出一个

勒让德公式：

c_p = \left\lfloor\frac{N}{p}\right\rfloor + \left\lfloor\frac{N}{p^2}\right\rfloor + \left\lfloor\frac{N}{p^3}\right\rfloor + \dots

为什么？#

$N! = 1 \times 2 \times 3 \times \dots \times N$ 中：

每 $p$ 个数里有一个是 $p$ 的倍数，贡献 1 个 $p$ → $\lfloor N/p \rfloor$
每 $p^2$ 个数里有一个额外再贡献 1 个 $p$ → $\lfloor N/p^2 \rfloor$
每 $p^3$ 个同理 → $\lfloor N/p^3 \rfloor$

1
N = 5, p = 2 时：
2
    5! = 1 × 2 × 3 × 4 × 5
3
             ↑       ↑
4
    ⌊5/2⌋ = 2（2 和 4）
5
    ⌊5/4⌋ = 1（4 多贡献一个）
6
    → 2 + 1 = 3，5! 含 2³  ✓

代码#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main() {
5
    int N;
6
    cin >> N;
7

8
    // 筛 ≤ N 的素数
9
    bitset<1000005> is_prime;
10
    is_prime.set();
11
    is_prime[0] = is_prime[1] = 0;
12
    for (int i = 2; i * i <= N; i++)
13
        if (is_prime[i])
14
            for (int j = i * i; j <= N; j += i)
15
                is_prime[j] = 0;
16

17
    // 勒让德公式：对每个素数直接算次数
18
    for (int p = 2; p <= N; p++) {
19
        if (!is_prime[p]) continue;
20

21
        int cnt = 0;
22
        long long power = p;
23
        while (power <= N) {
24
            cnt += N / power;
25
            power *= p;
26
        }
27
        cout << p << " " << cnt << "\n";
28
    }
29
}

本质#

朴素法是「先乘出阶乘，再拆开」——绕了远路。勒让德公式直接在阶乘层面统计每个质因子的贡献次数，完全跳过了对每个数的分解。

总结#

场景	武器
判别单个数（n ≤ 10¹²）	试除法到 √n
判别单个大数（n ≤ 2⁶⁴）	Miller-Rabin
批量生成 [1, N] 素数	埃氏筛 / 欧拉筛
大区间、小区间长度	分段筛（筛 √r → 筛区间）
N! 质因数分解	勒让德公式（筛素数表 + 指数求和）

五种武器，覆盖所有素数相关场景。

如果这篇文章对你有帮助，欢迎分享给更多人！

素数判定算法

https://caoyue.xin/posts/prime-testing/

作者

Colton/曹越

发布于

2026-07-05

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

纯新手入门 Agent 编程（Vibe Coding）指南——从零搭建你的 AI 编程助手

Colton Star Blog

一、试除法#

1.1 朴素版#

1.2 优化：只除到 √n#

1.3 毫秒级优化：6k ± 1 跳跃#

试除法小结#

二、埃氏筛与欧拉线性筛#

2.1 埃拉托斯特尼筛法（埃氏筛）#

2.2 常数优化：跳过偶数#

2.3 欧拉筛（线性筛）#

筛法对比#

三、Miller-Rabin 素性测试#

3.1 能处理多大？#

3.2 模板（直接复制用）#

3.3 底数记忆法#

3.4 怎么用？三步#

3.5 如果编译器不支持 __int128#

3.6 常见坑#

四、总览：什么时候用哪个#

五、实战案例：Primer Distance（POJ 2689）#

题目#

核心难点#

两种思路#

分段筛解法#

关键细节#

你的代码回顾#

六、阶乘分解（P10495）#

题目#

思路对比#

为什么？#

代码#

本质#

总结#

目录

3.5 如果编译器不支持 `__int128`#