目录

一、引言

二、埃拉托色尼筛法原理

2.1 基本思想

2.2 关键优化点

三、例题

四、代码实现

4.1 C++ 代码

4.2 详细解释

1. 初始化数组

2. 筛选质数

3. 统计质数个数

五、时间复杂度分析

为什么比朴素方法快？

空间复杂度分析

---

一、引言

质数是指大于 1 的自然数中，除了 1 和它本身以外，不能被其他正整数整除的数。判定一个数是否是质数是许多算法问题的基础，如数论、加密算法和数学建模等。

对于大规模的质数筛选，朴素方法的效率往往不够理想，而埃拉托色尼筛法是一种高效的筛选方法，能够在O(nlogn)的时间复杂度内筛选出n以内的所有质数

本文将详细介绍埃拉托色尼筛法的原理、代码实现，并结合一个蓝桥杯的相关题目进行解析

二、埃拉托色尼筛法原理

2.1 基本思想

埃拉托色尼筛法是一种利用标记倍数的方式来筛选质数的方法，基本思想如下：

1. 创建一个数组 nums，初始时假设所有数都是质数

2. 从 2 开始，逐个遍历 nums 数组，如果 nums[i] 仍然是 true，则 i 是质数

3. 将 i 的所有倍数（2i, 3i, 4i, ...）标记为 false，表示这些数不是质数

4. 继续遍历，直到 √N 为止

2.2 关键优化点

• 不需要检查 i 是否是质数：如果 nums[i] 仍然是 true，说明 i 是质数

• 从 i*i 开始标记非质数：因为比 i 小的数的倍数已经被前面的质数标记过

• 时间复杂度：O(nlogn)，远快于朴素方法O(nsqrt(n))

• 空间复杂度：O(n)，适用于较大范围的质数筛选

三、例题

9.质数 - 蓝桥云课

四、代码实现

4.1 C++ 代码

#include <iostream>
using namespace std;

const int N = 1e6; // 设置筛选上限
bool nums[N]; // 质数标记数组

int main() {
    fill(nums, nums + N, true); // 全部初始化为 true
    nums[0] = nums[1] = false;  // 0 和 1 不是质数

    for (int i = 2; i * i < N; i++) { // 遍历到 sqrt(N)
        if (nums[i]) { // 如果 i 仍然是质数
            for (int j = i * i; j < N; j += i) { // 从 i*i 开始标记
                nums[j] = false;
            }
        }
    }

    int sum = 0; // 统计质数个数
    for (int i = 2; i < N; i++) {
        if (nums[i]) {
            sum++;
            if (sum == 2019) { // 找到第2019个质数
                cout << i << endl;
                break;
            }
        }
    }

    return 0;
}

4.2 详细解释

1. 初始化数组

fill(nums, nums + N, true);

所有数先假设为质数（true），然后从 2 开始筛选

2. 筛选质数

for (int i = 2; i * i < N; i++) {
    if (nums[i]) {
        for (int j = i * i; j < N; j += i) {
            nums[j] = false;
        }
    }
}

• 遍历范围优化：只需遍历到 √N，因为更大的数如果是合数，必然已经被更小的质数筛选掉

• 从 i*i 开始标记：因为 2i, 3i, ... 这些数的倍数已经在前面的循环中被标记

3. 统计质数个数

for (int i = 2; i < N; i++) {
    if (nums[i]) {
        sum++;
        if (sum == 2019) {
            cout << i << endl;
            break;
        }
    }
}

找到第2019个质数并输出。

五、时间复杂度分析

埃拉托色尼筛法的时间复杂度为：O(nlogn）

为什么比朴素方法快？

• 朴素方法：遍历每个数，并用 O(sqrt(n))的复杂度检查是否为质数，总复杂度 O(nsqrt(n))

• 埃氏筛法：每个数只被其最小的质因子筛去一次，导致时间复杂度下降到 O(nlogn)

空间复杂度分析

• 朴素方法：不需要额外空间，但计算慢

• 埃氏筛法：需要一个 O(n) 级别的布尔数组，但计算快

• 适用范围：适用于 大规模质数筛选（如1e7级别）

总之，埃氏素数筛法筛法是一种高效筛选质数的方法，其核心是标记倍数，避免了重复计算，适用于大规模质数筛选