InoueMoby's Blog

前言

你能背出前 10 个素数吗？2, 3, 5, 7, 11, 13, 17, 19, 23, 29。没问题。前 100 个呢？也勉强可以硬背。但如果是”1 到 $10^7$ 之间有多少个素数”——你总不能一个一个试吧？

这就引出一个很自然的问题：有没有一种方法，能一次性把一个范围内所有素数都找出来，而不是对每个数单独判断？

两千多年前，古希腊的埃拉托斯特尼想出了一个绝妙的办法：想象一排从 2 开始的数字。先看第一个数 2——它是素数。好了，那 2 的倍数（4, 6, 8, 10, …）全都不是素数了，划掉。再看下一个没被划掉的数 3——它一定是素数（因为如果它有因子，早就被划掉了）。把 3 的倍数也划掉。再看 5、7……一直下去。最后留下来的全是素数。

这个方法叫埃氏筛。它不只是”找素数的工具”——更重要的是它背后的思想：与其逐个判断，不如批量排除。这个思想会在后面的很多算法中反复出现。

问题的本质

什么是素数？

一个大于 1 的整数 $n$ ，如果除了 1 和它本身之外没有其他因子，就叫素数。换句话说，素数是”不可分解”的数——它是整数世界的”原子”。

素数有一个不太直觉但极其重要的性质：如果 $p$ 是素数，且 $p$ 整除 $a \times b$ ，那么 $p$ 一定整除 $a$ 或整除 $b$ （至少整除其中一个）。

比如 $p = 3$ ：如果 $3 \mid (a \times b)$ ，那 $a$ 和 $b$ 中至少有一个是 3 的倍数。这听起来理所当然，但它只对素数成立—— $6 \mid (2 \times 3)$ 但 6 既不整除 2 也不整除 3，因为 6 不是素数。

这个性质的一个直接推论是：任何大于 1 的整数都可以唯一分解成素数的乘积。比如 $12 = 2^2 \times 3$ ， $60 = 2^2 \times 3 \times 5$ 。这叫算术基本定理。整个数论几乎都建立在这个定理之上。

素数判定：试除法

判断 $n$ 是不是素数，最直觉的方法是：用 $2, 3, 4, \ldots, n-1$ 一个一个去除，看有没有能整除的。

但有个关键优化：只需要试到 $\sqrt{n}$ 。

为什么？假设 $n = a \times b$ ，且 $a \le b$ 。那么 $a \times a \le a \times b = n$ ，所以 $a \le \sqrt{n}$ 。也就是说，如果 $n$ 有因子，至少有一个因子不超过 $\sqrt{n}$ 。所以我们只需要检查 $2$ 到 $\sqrt{n}$ 就够了。

比如判断 97 是不是素数： $\sqrt{97} \approx 9.8$ ，只需试 $2, 3, 4, 5, 6, 7, 8, 9$ 。97 不能被其中任何一个整除，所以 97 是素数。只需要 8 次除法，而不是 95 次。

素因数分解

算术基本定理告诉我们每个数都能唯一分解成素数的乘积。那怎么实际分解呢？

方法和素数判定一样——从 2 开始试除，试到 $\sqrt{n}$ 。不同之处在于：找到一个素因子后，要把它除干净，然后继续找下一个。

比如分解 $360$ ：

步骤	当前 $n$	试除 $p$	$n \bmod p$	操作	分解结果
1	360	2	0	除以 2	$2 \times$
2	180	2	0	除以 2	$2^2 \times$
3	90	2	0	除以 2	$2^3 \times$
4	45	2	1	换下一个
5	45	3	0	除以 3	$2^3 \times 3 \times$
6	15	3	0	除以 3	$2^3 \times 3^2 \times$
7	5	3	2	换下一个
8	5	4	跳过（4 不是素数）
9	5	5	$5 \times 5 > 5$ ，循环结束	剩余 $n=5 > 1$	$2^3 \times 3^2 \times 5$

最终 $360 = 2^3 \times 3^2 \times 5$ 。验证： $8 \times 9 \times 5 = 360$ 。✓

注意步骤 8：虽然 4 不是素数，但不用担心——4 的素因子 2 早就被除干净了，所以 $n \bmod 4 \neq 0$ ，自然会跳过。也就是说，不需要事先知道哪些数是素数，只要从小到大试除就行。

// 素因数分解，返回 {(素因子, 指数), ...}
vector<pair<long long, int>> factorize(long long n) {
    vector<pair<long long, int>> factors;
    for (long long p = 2; p * p <= n; p++) {  // ① 枚举到 √n
        if (n % p == 0) {
            int cnt = 0;
            while (n % p == 0) {
                n /= p;      // ② 除干净
                cnt++;        // ③ 计数这个素因子的幂次
            }
            factors.push_back({p, cnt});
        }
    }
    if (n > 1)                  // ④ 剩下的大于 √n 的素因子（最多一个）
        factors.push_back({n, 1});
    return factors;
}

① 枚举到 $\sqrt{n}$ 就够了——和素数判定同样的理由：如果 $n$ 还有因子，至少有一个 $\le \sqrt{n}$ 。
② 内层 while 把当前素因子除干净。比如 $n = 360$ ，遇到 $p = 2$ 时连除三次， $n$ 变成 45。
④ 循环结束后如果 $n > 1$ ，那这个 $n$ 本身就是一个大于 $\sqrt{\text{原}n}$ 的素因子。为什么最多一个？因为如果还有两个大于 $\sqrt{n}$ 的素因子，它们的乘积就超过 $n$ 了。

从”逐个判断”到”批量筛选”

试除法对单个数很快： $O(\sqrt{n})$ 。但如果要找出 $1$ 到 $10^7$ 之间所有素数，对每个数都用试除法，总共 $O(n\sqrt{n}) \approx 3 \times 10^{10}$ 次运算——太慢了。

埃氏筛的思路完全不同：它不判断任何数是不是素数，而是直接把合数划掉。具体来说，如果 $p$ 是素数，那么 $2p, 3p, 4p, \ldots$ 都不是素数。所以只需要遍历每个素数 $p$ ，把它的倍数划掉就行了。

理论 + 代码

素因数分解的简单应用

素因数分解是很多数论算法的基础。几个例子：

求约数个数： $n = p_1^{a_1} \times p_2^{a_2} \times \cdots$ ，约数个数 $= (a_1+1)(a_2+1)\cdots$ 。比如 $360 = 2^3 \times 3^2 \times 5^1$ ，约数个数 $= 4 \times 3 \times 2 = 24$ 。
求约数之和： $\prod \frac{p_i^{a_i+1}-1}{p_i-1}$ 。
求 GCD/LCM： $\gcd(a,b)$ 取每个素因子的最小幂次， $\text{lcm}(a,b)$ 取最大幂次。
求欧拉函数（02-07 会详细讲）： $\varphi(n) = n \prod_{p \mid n}(1 - 1/p)$ 。

素数判定（试除法）

bool is_prime(long long n) {
    if (n < 2) return false;             // ① 0 和 1 不是素数
    for (long long i = 2; i * i <= n; i++) {  // ② 枚举到 √n
        if (n % i == 0) return false;     // ③ i 能整除 n，n 不是素数
    }
    return true;                          // ④ 没找到因子，是素数
}

① 小于 2 的数不是素数。这是边界条件。
② i * i <= n 等价于 i <= sqrt(n)，但避免了浮点运算。注意 i 必须是 long long——当 $n$ 接近 $10^{12}$ 时，i 接近 $10^6$ ，i * i 接近 $10^{12}$ ，用 int 会溢出。
③ 只要找到一个因子就返回 false。不需要继续找了。
④ 循环结束还没找到因子，说明 $n$ 是素数。

埃氏筛

bool not_prime[10000010];  // not_prime[i] = true 表示 i 被划掉了

void sieve(int n) {
    not_prime[0] = not_prime[1] = true;  // ① 0 和 1 不是素数
    for (int i = 2; i <= n; i++) {
        if (not_prime[i]) continue;       // ② 已被划掉，跳过
        // ③ i 没被划掉，说明 i 是素数
        for (long long j = (long long)i * i; j <= n; j += i)
            not_prime[j] = true;          // ④ 把 i 的倍数划掉
    }
}

走一遍具体过程（筛 $1$ 到 $30$ ）：

步骤	当前素数 $p$	划掉的数
1	2	4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30
2	3	9, 15, 21, 27
3	5	25
4	7	（7×7=49 > 30，不划任何数）

注意：步骤 2 划掉的是 9, 15, 21, 27——不是 6, 12, 18, 24, 30，因为那些已经在步骤 1 被划掉了。步骤 3 划掉的是 25——不是 10, 15, 20（已被划），只剩 25。

最终留下的：2, 3, 5, 7, 11, 13, 17, 19, 23, 29。共 10 个素数。✓

为什么从 $i \times i$ 开始而不是 $2i$ ？

因为 $2i$ 在 $i=2$ 时就被划掉了， $3i$ 在 $i=3$ 时被划掉了…… $(i-1) \times i$ 在更早的轮次被划掉了。第一个还没被划掉的 $i$ 的倍数就是 $i \times i$ 。这个优化让总操作数从 $O(n \log n)$ 降到 $O(n \log \log n)$ 。

$O(n \log \log n)$ 是什么概念？当 $n = 10^7$ 时， $\log \log n \approx \log(23) \approx 3$ 。所以总共约 $3 \times 10^7$ 次操作——远快于试除法的 $3 \times 10^{10}$ 。

线性筛（欧拉筛）

埃氏筛还有一个小问题：同一个合数可能被多次标记。比如 30 被 2 划了一次、被 3 又划了一次、被 5 又划了一次。能不能让每个合数只被划一次？

线性筛做到了。核心思想：每个合数只被它的最小素因子划掉。

int primes[10000010], cnt;  // primes[] 存所有素数，cnt 是素数个数
bool not_prime[10000010];

void linear_sieve(int n) {
    for (int i = 2; i <= n; i++) {
        if (!not_prime[i])
            primes[cnt++] = i;       // ① i 是素数，加入素数列表

        for (int j = 0; j < cnt && (long long)i * primes[j] <= n; j++) {
            not_prime[i * primes[j]] = true;  // ② 用 i × p[j] 标记合数

            if (i % primes[j] == 0) break;    // ③ 关键！
        }
    }
}

③ 是整个算法的灵魂。让我解释为什么这里要 break：

假设当前 $i = 6$ ，素数列表是 [2, 3, 5]。

$j=0$ : 标记 $6 \times 2 = 12$ 。 $6 \bmod 2 = 0$ ，break。
我们没有标记 $6 \times 3 = 18$ 和 $6 \times 5 = 30$ 。

为什么？因为 6 是 2 的倍数，所以 $6 \times 3 = 2 \times 9$ ——18 应该在后面 $i = 9$ 时被 $p = 2$ 划掉。如果现在用 $p = 3$ 划了 18，那 18 就被划了两次（一次被 3，一次被 2）。更严重的是，这会破坏”每个合数只被最小素因子划掉”的保证。

更一般地：当 $i$ 是 $p_j$ 的倍数时， $i \times p_{j+1}$ 的最小素因子是 $p_j$ （而不是 $p_{j+1}$ ），所以它应该在 $p_j$ 划的时候被划掉，而不是现在。

线性筛的时间是严格 $O(n)$ ——每个合数恰好被标记一次。同时，它还有一个副产品：primes[] 数组按顺序存储了所有素数，这在后面很多算法中都会用到。

例题

例题 1：M&A 012 — Primality Test（★1）

题目：给定整数 $N$ ，判断 $N$ 是否为素数。是则输出 Yes，否则输出 No。

数据范围： $2 \le N \le 10^{12}$

—— AtCoder M&A 012

思路：试除法——从 2 到 $\sqrt{N}$ 检查是否有因子。 $N \le 10^{12}$ 时 $\sqrt{N} \le 10^6$ ，可以接受。

代码：

#include <cstdio>
using namespace std;

bool is_prime(long long n) {
    for (long long i = 2; i * i <= n; i++) {  // ① 试到 √n
        if (n % i == 0) return false;          // ② 找到因子，不是素数
    }
    return true;
}

int main() {
    long long N;
    scanf("%lld", &N);
    printf("%s\n", is_prime(N) ? "Yes" : "No");
}

逐行解析：

① i * i <= n 等价于 i <= sqrt(n)，但避免浮点精度问题。i 必须是 long long，因为 $N \le 10^{12}$ 时 $i^2$ 可能超过 int。

例题 2：M&A 011 — Print Prime Numbers（★1）

题目：给定 $N$ ，输出 1 到 $N$ 之间的所有素数，每行一个。

数据范围： $1 \le N \le 500000$

—— AtCoder M&A 011

思路：如果对每个数做试除法， $O(N\sqrt{N}) \approx 3.5 \times 10^8$ ，勉强能过。但用埃拉托斯特尼筛法只需 $O(N \log \log N)$ ，快得多。

代码：

#include <cstdio>
using namespace std;

bool not_prime[500010];    // true = 不是素数

int main() {
    int N;
    scanf("%d", &N);

    not_prime[0] = not_prime[1] = true;    // ① 0 和 1 不是素数
    for (int i = 2; i <= N; i++) {
        if (!not_prime[i]) {               // ② i 是素数
            for (int j = 2 * i; j <= N; j += i)  // ③ 标记 i 的所有倍数
                not_prime[j] = true;
        }
    }

    for (int i = 2; i <= N; i++)
        if (!not_prime[i])
            printf("%d\n", i);
}

逐行解析：

②③ 如果 i 没被标记，说明它是素数。然后从 $2i$ 开始，每隔 $i$ 标记一个——这些全是 $i$ 的倍数，不是素数。

例题 3：M&A 097 — Primes in an Interval（★3）

题目：给定 $L$ 和 $R$ ，求 $L$ 到 $R$ 之间的素数个数。

数据范围： $1 \le L \le R \le 10^{12}$ ， $R - L \le 500000$

—— AtCoder M&A 097

思路： $R$ 最大 $10^{12}$ ，直接筛到 $R$ 不可能。但 $R - L \le 5 \times 10^5$ ，可以用区间筛：先筛出 $\sqrt{R}$ 以内的素数（最多 $10^6$ ），然后用这些素数去标记 $[L, R]$ 中的合数。

代码：

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int MAXV = 1000010;
bool not_prime[MAXV];
bool is_composite[500010];  // [L, R] 中的合数标记

int main() {
    long long L, R;
    scanf("%lld%lld", &L, &R);

    // ① 筛出 √R 以内的素数
    for (long long i = 2; i * i <= R; i++) {
        if (!not_prime[i]) {
            for (long long j = i * i; j < MAXV && j <= R; j += i)
                not_prime[j] = true;
        }
    }

    // ② 用这些素数标记 [L, R] 中的合数
    for (long long i = 2; i * i <= R; i++) {
        if (not_prime[i]) continue;
        // 最小的 >= L 的 i 的倍数
        long long start = max(i * i, ((L + i - 1) / i) * i);  // ③ 对齐到 i 的倍数
        for (long long j = start; j <= R; j += i)
            is_composite[j - L] = true;  // ④ 偏移存到数组
    }

    int cnt = 0;
    for (long long i = max(2LL, L); i <= R; i++) {
        if (!is_composite[i - L])
            cnt++;
    }
    printf("%d\n", cnt);
}

逐行解析：

① 筛 $[2, \sqrt{R}]$ 中的素数。 $\sqrt{10^{12}} = 10^6$ 。
③ ((L + i - 1) / i) * i：最小的 $\ge L$ 的 $i$ 的倍数（向上取整乘 $i$ ）。但要至少从 $i \times i$ 开始，避免 $i$ 本身被标记。
④ j - L 把 $[L, R]$ 映射到 $[0, R-L]$ ，适配数组大小。

例题 4：M&A 014 — Factorization（★1）

题目：给定整数 $N$ ，输出 $N$ 的所有素因子（按从小到大的顺序，重复的因子重复输出）。

数据范围： $2 \le N \le 10^{12}$

—— AtCoder M&A 014

思路：从 2 到 $\sqrt{N}$ 试除，每除尽一个因子就输出。

代码：

#include <cstdio>
using namespace std;

int main() {
    long long N;
    scanf("%lld", &N);

    for (long long i = 2; i * i <= N; i++) {  // ① 试到 √N
        while (N % i == 0) {                   // ② 除尽所有 i
            printf("%lld ", i);
            N /= i;
        }
    }
    if (N > 1)                                 // ③ 剩下的大于1的N本身是素因子
        printf("%lld", N);
    printf("\n");
}

逐行解析：

② while 不是 if：同一个因子可能多次出现（如 $12 = 2^2 \times 3$ ）。
③ 如果最后 $N > 1$ ，说明 $N$ 本身是一个大于 $\sqrt{原N}$ 的素因子。

例题 5：Tessoku Book — A26 Prime Check

题目：给定整数 $N$ ，判断 $N$ 是否为素数。

数据范围： $1 \le N \le 10^{12}$

—— AtCoder Tessoku Book A26

思路：和例题 1 一模一样——试除法。用不同的代码风格再写一遍加深印象。

代码：

#include <cstdio>
using namespace std;

int main() {
    long long N;
    scanf("%lld", &N);

    if (N < 2) { printf("No\n"); return 0; }

    bool prime = true;
    for (long long i = 2; i * i <= N; i++) {
        if (N % i == 0) { prime = false; break; }
    }
    printf("%s\n", prime ? "Yes" : "No");
}

参考文献

理论讲义 — AtCoder Algorithm Lectures

素数の性質（難易度 3）

教材讲解 — 競技プログラミングの鉄則第 5 章

5.1 B26 Output Prime Numbers（埃氏筛解说）

基础练习 — アルゴリズムと数学演習問題集

系统练习 — 競技プログラミングの鉄則

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

素数与筛法

怎么快速找出1到N之间所有的素数——埃氏筛与线性筛

前言

问题的本质

什么是素数？

素数判定：试除法

素因数分解

从”逐个判断”到”批量筛选”

理论 + 代码

素因数分解的简单应用

素数判定（试除法）

埃氏筛

线性筛（欧拉筛）

例题

例题 1：M&A 012 — Primality Test（★1）

例题 2：M&A 011 — Print Prime Numbers（★1）

例题 3：M&A 097 — Primes in an Interval（★3）

例题 4：M&A 014 — Factorization（★1）

例题 5：Tessoku Book — A26 Prime Check

参考文献

系列索引

素数与筛法