CSP WIKI

简介与概述、功能介绍

埃拉托斯特尼筛法（Sieve of Eratosthenes），简称埃氏筛，是一种用于找出一定范围内所有素数的经典算法。它的核心功能是高效地标记出指定区间内的合数，从而筛选出其中的素数。

算法原理详解

埃氏筛法的基本思想是从 2 开始，将每个素数的倍数都标记为合数，剩下未被标记的数就是素数。具体步骤如下：

初始化：创建一个布尔类型的数组 isPrime，长度为要筛选的范围 n + 1，并将数组中所有元素初始化为 true，表示一开始假设所有数都是素数。
筛选过程：
- 从 2 开始，因为 2 是最小的素数，将 2 的倍数（4、6、8、…）标记为 false，表示它们是合数。
- 找到下一个未被标记的数，也就是 3，它是素数，将 3 的倍数（6、9、12、…）标记为 false。
- 重复这个过程，直到遍历到 $\sqrt{n}$ 。这是因为如果一个数 $n$ 是合数，那么它一定有一个不大于 $\sqrt{n}$ 的因子。
输出结果：遍历 isPrime 数组，将值为 true 的下标对应的数输出，这些数就是筛选出的素数。

演示

经典例题及代码实现

题面

给定一个正整数 $n$ ，要求找出小于等于 $n$ 的所有素数，并按从小到大的顺序输出。

输入输出样例

输入：一个正整数 $n$ 。

示例输入：

输出：按从小到大的顺序输出小于等于 $n$ 的所有素数，每个素数占一行。

示例输出：

代码实现

示例代码

#include <iostream>
using namespace std;
 
const int MAXN = 1000005;
bool isPrime[MAXN];
 
// 埃拉托斯特尼筛法
void sieve(int n) {
    // 初始化所有数为素数
    for (int i = 2; i <= n; i++) {
        isPrime[i] = true;
    }
    // 筛选过程
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    // 输出素数
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            cout << i << endl;
        }
    }
}
 
int main() {
    int n;
    // 读入一个正整数
    cin >> n;
    sieve(n);
    return 0;
}

代码解释

isPrime 数组用于标记每个数是否为素数。
sieve 函数实现了埃氏筛法的核心逻辑，先将所有数初始化为素数，然后从 2 开始筛选，将素数的倍数标记为合数，最后输出所有素数。
在 main 函数中，读入要筛选的范围 $n$ ，并调用 sieve 函数进行筛选和输出。

分析与总结

埃拉托斯特尼筛法是一种简单而高效的素数筛选算法，时间复杂度为 $O(n \log \log n)$ ，空间复杂度为 $O(n)$ 。它的实现相对简单，在信息学竞赛中，对于处理一定范围内素数的查找问题非常实用。不过，当范围非常大时，埃氏筛法可能会存在一定的局限性，此时可以考虑使用更高级的素数筛选算法，如线性筛法（欧拉筛法）。但对于大多数竞赛题目，埃氏筛法已经能够满足需求。

例题

Status

Problem

素数筛法