当前没有测试数据。

埃拉托色尼筛法（Sieve of Eratosthenes）介绍

一、算法背景

埃拉托色尼筛法（Sieve of Eratosthenes）是一种**高效的筛选质数（素数）**的算法，最早由古希腊数学家埃拉托色尼提出，至今仍广泛应用于算法竞赛、数学教学与工程实现中。

该算法的核心思想是：

将不大于某个整数 $n$ 的所有合数用最小的质数的倍数剔除，剩下的数即为所有的质数。

二、算法原理

对于任意一个大于 1 的正整数 $n$，我们要找出所有不超过 $n$ 的质数。埃氏筛的基本步骤如下：

1. 初始化一个布尔数组 is_prime[2..n]，全部置为 true，表示一开始假设所有数都是质数；
2. 从 $i = 2$ 开始，如果 $i$ 是质数（is_prime[i] == true），则将所有 $i$ 的倍数（从 $i^2$ 开始）标记为非质数；
3. 重复步骤 2，直到 $i^2 > n$。

三、算法实现（C++ 示例）

const int N = 1e7;
bool is_prime[N + 1];

void sieve(int n) {
    for (int i = 2; i <= n; i++) is_prime[i] = true;

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

• is_prime[i] == true 表示 $i$ 是质数；
• 时间复杂度为 $O(n \log \log n)$，空间复杂度为 $O(n)$；
• 可以扩展用于快速统计质数个数、构造前缀和、线性筛基础等。

https://www.visnos.com/demos/sieve-of-eratosthenes?utm_source=chatgpt.com