1. 核心原理：素数的定义与逆向思维

直观理解： 通常我们判断一个数是否为素数，是看它能否被比它小的数整除（试除法）。而埃氏筛采用的是逆向思维：

如果我们要找范围 $[2, n]$ 内所有的素数，不如先把所有的合数找出来并“筛”掉，剩下的就是素数。

算法流程：

1. 我们把 $2$ 到 $n$ 的所有数字列出来，假设它们一开始都是素数（del 数组全为 0）。
2. 从最小的素数 $2$ 开始。
3. 核心步骤：如果当前数字 $i$ 没有被筛掉（del[i] == 0），说明它是一个素数。
4. 筛除倍数：将 $i$ 的所有倍数（$2i, 3i, 4i \dots$）标记为合数（del[j] = 1），因为它们肯定包含因子 $i$。
5. 找到下一个没有被标记的数字，重复步骤 3 和 4，直到遍历完所有数字。

2. 代码深度解析与关键优化

在你的博客中，这一部分是区分“新手代码”和“竞赛代码”的关键。你的代码中包含了两个非常重要的优化点。

优化点一：内层循环的起点 j = i * i

        
1
2

        for(int j=i*i; j<=n; j+=i) del[j] = 1;

    

问题： 为什么内层循环从 $i^2$ 开始，而不是 $2i$ 开始？ 解释： 当我们在筛 $i$ 的倍数时，比 $i^2$ 小的倍数（例如 $2 \times i, 3 \times i, \dots, (i-1) \times i$）其实已经被比 $i$ 小的素数筛过了。

• 例如：当 $i=5$ 时，我们不需要筛 $2 \times 5 = 10$，因为在 $i=2$ 时，$10$ 已经被筛掉了。
• 我们也不需要筛 $3 \times 5 = 15$，因为在 $i=3$ 时，$15$ 已经被筛掉了。
• 所以，$i$ 的倍数只需要从 $i \times i$ 开始筛。这极大地减少了重复标记的次数。

优化点二：防溢出与提前终止 if( i > n / i ) continue;

        
1
2

        if( i > n / i ) continue;

    

解释： 这个判断等价于 $i > \sqrt{n}$（或者 $i^2 > n$）。

• 结合优化点一，因为内层循环是从 $i*i$ 开始的。
• 如果 $i^2$ 已经超过了 $n$，那么内层循环根本不会执行。
• 技巧： 使用除法 n / i 而不是乘法 i * i 来判断，是为了防止 i * i 计算结果超过 int 范围导致整数溢出（Integer Overflow）。这是竞赛中非常实用的细节。

3. 时间复杂度分析

这是体现博客深度的部分。

• 朴素做法（试除法）：对每个数做试除，复杂度是 $O(n\sqrt{n})$。
• 埃氏筛：
  • 对于素数 2，我们筛去 $n/2$ 个数。
  • 对于素数 3，我们筛去 $n/3$ 个数。
  • 对于素数 5，我们筛去 $n/5$ 个数。
  • …
  • 总的操作次数约为 $n \times (\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + \dots)$。
  • 根据数学上的梅尔滕斯第二定理 (Mertens’ 2nd Theorem)，这个素数倒数之和发散的速度非常慢，近似于 $\ln(\ln n)$。

结论： 埃氏筛的时间复杂度为 $O(n \log \log n)$。 这个复杂度非常接近线性 $O(n)$。在 $n = 10^7$ 甚至 $10^8$ 的级别下，它运行得非常快，基本能满足大部分算法竞赛（如 Codeforces, ICPC）中对预处理素数的需求。

4. 博客写作建议框架

如果要发到 CSDN、知乎或个人博客，建议按照以下结构：

1. 引言：通过“如何快速找出10万以内的所有素数？”引入话题。
2. 暴力法的局限：简述 $O(n\sqrt{n})$ 在大数据量下的超时问题。
3. 埃氏筛图解：用一张简单的表格图（或者文字列表），演示筛 2、筛 3 的过程。
4. 代码实现：贴出你的代码。
5. 核心难点剖析：(重点) 解释为什么 j 从 i*i 开始。
6. 复杂度证明：简单提一下 $O(n \log \log n)$。
7. 扩展阅读（可选）：提一句“虽然埃氏筛很快，但仍有重复标记（如 6 会被 2 和 3 标记两次），如果要追求极致的 $O(n)$，可以学习欧拉筛（线性筛）”。

代码

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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

const int maxn = 1e5+5;
bool del[maxn]; // 0 表示没有删除
vector<int> prime;

//埃式筛法
/* 原理: 
 *  - 2是最小的的素数,2的k倍都不是素数,k>=2
 *  - 下一个没有被筛掉的数是3,所以3是素数(原理:合数一定可以拆出一个小于自己的素数因子)
 *      - 删除3的k>=3倍数
 *  - 4 被删除,不用岀它的倍数
 *  - ....
 * */
void E_prime(int n){
    //memset(del,0,sizeof(del));
    for(int i=2;i<=n;i++){
        if( del[i] == 0){
            prime.push_back(i);
            if( i > n / i ) continue; //防溢出
            for(int j=i*i;j<=n;j+=i) del[j] = 1;
        }
    }
}

int main(){
    E_prime(100); // 求100内的素数
    for (const auto& e : prime) {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

    

这是一篇为您准备好的技术博客草稿。采用了清晰的 Markdown 格式，您可以直接复制到 CSDN、博客园、知乎或您的个人 Hugo/Hexo 博客中。

【算法竞赛】素数筛法入门：详解埃拉托斯特尼筛法 (Sieve of Eratosthenes)

1. 引言

在算法竞赛（如 Codeforces, ICPC, 蓝桥杯）中，数论题目非常常见。而数论题往往离不开一个最基础的问题：

如何快速找出 $1$ 到 $n$ 之间的所有素数？

如果 $n$ 比较小（比如 $100$），我们完全可以手算。但如果题目要求 $n$ 达到 $10^5$ 甚至 $10^7$ 级别，应该怎么办？今天我们就来深入讲解一种历史悠久且非常高效的算法——埃拉托斯特尼筛法（简称“埃氏筛”）。

2. 暴力法的局限

最直观的思路是“试除法”。即对于 $1$ 到 $n$ 的每一个数 $x$，我们都判断它是不是素数。判断的方法是尝试除以 $2$ 到 $\sqrt{x}$ 之间的所有整数。

        
1
2
3
4
5
6
7
8
9

        // 伪代码：暴力判断
for (int i = 2; i <= n; i++) {
    bool is_prime = true;
    for (int j = 2; j * j <= i; j++) {
        if (i % j == 0) is_prime = false;
    }
    if (is_prime) primes.push_back(i);
}

    

时间复杂度分析： 对于每个数 $i$，判断素数的复杂度是 $O(\sqrt{i})$。总的时间复杂度是 $\sum_{i=1}^{n} \sqrt{i} \approx O(n\sqrt{n})$。

• 当 $n = 10^5$ 时，计算量大约是 $3 \times 10^7$，勉强可以接受。
• 当 $n = 10^7$ 时，计算量高达 $3 \times 10^{10}$，而通常竞赛题目限制 $1$ 秒（约 $10^8$ 次运算），这会导致 TLE (Time Limit Exceeded)。

因此，我们需要一种构造性的方法，而不是验证性的方法。

3. 埃氏筛图解

埃氏筛的核心思想是“逆向思维”： 与其费力判断一个数是不是素数，不如把所有的合数都找出来并“筛掉”，剩下的自然就是素数。

原理：

1. 如果 $x$ 是素数，那么 $x$ 的倍数 ($2x, 3x, 4x \dots$) 一定是合数。
2. 我们从最小的素数 $2$ 开始，把它的倍数全部标记为“删除”。
3. 找到下一个没被删除的数（它是 $3$），它一定是素数，再把 $3$ 的倍数全部标记为“删除”。
4. 重复这个过程。

图解演示（以 $n=20$ 为例）：

初始状态：2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

1. 筛 $2$：$2$ 未被标记 $\to$ 素数。 筛掉 $2$ 的倍数：4, 6, 8, 10, 12, 14, 16, 18, 20。 剩余：2 3 [4] 5 [6] 7 [8] 9 [10] 11 [12] 13 [14] 15 [16] 17 [18] 19 [20]

2. 筛 $3$：$3$ 未被标记 $\to$ 素数。 筛掉 $3$ 的倍数：6 (已删), 9, 12 (已删), 15, 18 (已删)。 剩余：2 3 [4] 5 [6] 7 [8] [9] [10] 11 [12] 13 [14] [15] [16] 17 [18] 19 [20]

3. 筛 $4$：$4$ 已经被标记，跳过。

4. 筛 $5$：$5$ 未被标记 $\to$ 素数。 筛掉 $5$ 的倍数：10, 15, 20 (都已被删)。

最终剩下的就是素数序列：2, 3, 5, 7, 11, 13, 17, 19。

4. 代码实现

下面是经过优化的 C++ 模板代码。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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

const int maxn = 1e5+5; // 根据题目要求设定范围
bool del[maxn];         // 标记数组，0 表示未删除（是素数），1 表示已删除（是合数）
vector<int> prime;      // 存储素数的容器

void E_prime(int n){
    // 注意：如果是局部变量，del数组需要 memset(del, 0, sizeof(del));
    // 全局变量默认为 0，所以这里可以直接用
    
    for(int i = 2; i <= n; i++){
        if(del[i] == 0){ // 如果 i 没被筛掉，说明 i 是素数
            prime.push_back(i);
            
            // 【优化2】防溢出检查 & 提前终止
            // 如果 i*i 已经超过 n，则没必要去筛它的倍数了
            if( i > n / i ) continue; 
            
            // 【优化1】从 i*i 开始筛
            for(int j = i * i; j <= n; j += i){
                del[j] = 1;
            }
        }
    }
}

int main(){
    E_prime(100); // 求 100 内的素数
    for (const auto& e : prime) {
        cout << e << " ";
    }
    cout << endl;
    return 0;
}

    

5. 核心难点剖析（关键优化）

很多初学者的埃氏筛代码不够高效，因为忽略了两个极其重要的优化细节：

优化一：内层循环从 j = i * i 开始

        
1
2

        for(int j = i * i; j <= n; j += i)

    

为什么不是 2 * i？ 当我们在筛 $i$ 的倍数时，比 $i$ 小的倍数（例如 $2 \times i, 3 \times i$）其实在之前处理素数 $2$ 和 $3$ 的时候就已经被筛掉了。 例如，当 $i=5$ 时，我们不需要筛 $10 (2\times5)$ 和 $15 (3\times5)$，直接从 $25 (5\times5)$ 开始即可。这极大地减少了重复赋值的操作。

优化二：防溢出判断 if( i > n / i ) continue;

这行代码等价于判断 $i^2 > n$。

1. 逻辑上：结合优化一，如果 $i^2 > n$，说明内层循环根本不会执行，所以可以直接跳过后续的筛过程。
2. 工程上：直接写 i * i > n 可能会导致整数溢出（Integer Overflow），尤其是当 $i$ 接近 $46340$ （即 $\sqrt{2^{31}-1}$）时。使用除法 n / i 是更安全的写法。

6. 复杂度证明

埃氏筛的时间复杂度并非直觉上的 $O(n)$ 或 $O(n^2)$。

• 对于素数 $2$，循环执行 $n/2$ 次。
• 对于素数 $3$，循环执行 $n/3$ 次。
• 对于素数 $5$，循环执行 $n/5$ 次。
• …

总操作次数约为：

根据数学上的 Mertens’ 2nd Theorem（梅尔滕斯第二定理），素数倒数之和发散的速度非常慢，约为 $\ln(\ln n)$。

因此，埃氏筛的时间复杂度为：

这是一个非常接近线性的复杂度。对于 $10^7$ 的数据，$\log \log n$ 极小，算法运行极其迅速。

7. 扩展阅读

虽然埃氏筛已经足够快了，但细心的同学会发现它仍然存在重复标记的问题。 比如数字 $12$：

• 在 $i=2$ 时，被标记了一次 ($2 \times 6$)。
• 在 $i=3$ 时，又被标记了一次 ($3 \times 4$)。

如果想要追求极致的性能，达到严格的线性时间复杂度 $O(n)$，即每个合数只被它的最小质因子筛一次，可以进一步学习欧拉筛（Linear Sieve）。

但在大多数竞赛题目中，简单好写的埃氏筛已经完全够用了。

时间复杂度

调和级数

题目

• CF-776B Sherlock and his girlfriend tags: [数论,埃式筛]
• 完美应用了筛法的框架 CF757B CF-757B Bash's Big Day tags: [数论,埃式筛]