【数论、线性筛】实现一个素数筛

题意

给定一个正整数 $n$，要求找出从 $1$ 到 $n$ 范围内的所有素数。 数据范围：$1 \le n \le 10^7$。

题目分析

本题的目标是求解一个指定范围内的所有素数，是典型的素数筛问题。经典的埃拉托斯特尼筛法（Sieve of Eratosthenes）通过对每个素数 $p$ 标记其所有倍数（$2p, 3p, \dots$）为合数来实现，其时间复杂度为 $O(n \log \log n)$。该算法的瓶颈在于一个合数可能被其多个不同的素因子重复标记。例如，$12$ 会被 $2$ 和 $3$ 分别标记一次。为了达到线性时间复杂度，我们引入欧拉筛法（Euler's Sieve），也称线性筛。其核心思想是确保每一个合数都只被其最小的素因子筛选（标记）一次。

我们维护一个布尔数组 $v$，$v[i]$ 为真表示 $i$ 是合数。同时，我们用一个数组 $p$ 存储已经找到的素数。我们从 $2$ 到 $n$ 遍历所有数字 $i$。

1. 如果 $v[i]$ 为假，说明 $i$ 没有被任何比它小的数的素因子筛过，因此 $i$ 是一个素数，我们将其加入素数数组 $p$。
2. 接着，我们遍历已找到的素数数组 $p$。对于每一个素数 $p_j$，我们将 $i \times p_j$ 标记为合数，即 $v[i \times p_j] = \text{true}$。这是因为 $i \times p_j$ 显然是一个合数，且它的一个素因子是 $p_j$。
3. 最关键的一步是保证每个合数只被其最小素因子筛掉。当我们遍历素数 $p_j$ 时，如果发现 $i$ 是 $p_j$ 的倍数，即 $i \pmod{p_j} = 0$，我们必须立即停止对当前 $i$ 的进一步筛选。这是因为 $p_j$ 是 $i$ 的最小素因子（如果不是，那么 $i$ 在早先的步骤中就已经被一个更小的素因子处理，并触发了 break）。对于任何一个比 $p_j$ 更大的素数 $p_k$ ($k>j$)，合数 $i \times p_k$ 的最小素因子是 $p_j$（因为 $i = k' \times p_j$, 所以 $i \times p_k = k' \times p_j \times p_k$），而不是 $p_k$。根据我们的核心思想，这个合数 $i \times p_k$ 应该由 $p_j$ 来筛。它会在后续外层循环遍历到 $i' = i/p_j \times p_k$ 时，被内层循环的 $p_j$ 筛掉。因此，为了避免重复筛选，我们在此处 break。

通过上述机制，我们保证了每个合数 $C$ 都唯一地被其最小素因子 $p_{min}$ 以 $C = p_{min} \times (C/p_{min})$ 的形式筛掉。外层循环变量为 $i = C/p_{min}$ 时，内层循环遍历到 $p_j = p_{min}$ 时完成筛选。由于每个数作为 $i$ 和 $p_j$ 的组合只被访问常数次，总时间复杂度为 $O(n)$。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1e7 + 5;

int n;
int p[N]; // 存储素数
bool v[N]; // v[i] = true 表示 i 是合数
int cnt; // 素数的数量

void sve(int num) {
    for (int i = 2; i <= num; ++i) {
        if (!v[i]) {
            p[cnt++] = i; // i 是素数
        }

        // 遍历已有素数来筛掉合数
        for (int j = 0; j < cnt && i <= num / p[j]; ++j) {
            v[i * p[j]] = true; // i * p[j] 是合数

            // 关键：保证每个合数只被其最小质因子筛一次
            if (i % p[j] == 0) {
                break;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    
    sve(n);
    
    // 打印找到的素数数量
    cout << cnt << endl;
    
    // 打印所有素数
    // for (int i = 0; i < cnt; ++i) {
    //     cout << p[i] << " ";
    // }
    // cout << endl;

    return 0;
}