跳到主要内容

AcWing 868. 筛质数

本节目标

用线性筛在一次遍历中获得范围内递增的质数表。

这是质数判定与筛法中的批量版本：题目只要求质数个数，但核心函数保留递增质数表，便于后续题复用。

查看 AcWing 原题

题意与约束​

给定上界 n，输出 1..n 内质数的个数。1 以内没有质数；同一个质数不能因多条筛除路径而重复计数。

第一反应与瓶颈​

逐个调用试除法能得到正确答案，但总复杂度约为 O(n√n)。埃氏筛已能从质数的倍数出发减少工作；本题进一步使用线性筛，使每个合数只被标记一次。

数学关系与算法推导​

按 number = 2..n 扫描。未被标为合数的 number 就是一个新质数，加入递增表。再用表内每个 prime 标记 number × prime；一旦 prime 整除 number，该乘积的最小质因子已确定为 prime，停止内层循环。

标记前先判断 prime <= n / number，因此无需先计算可能超过范围或溢出的乘积。这里不使用 sqrt 作为循环条件：筛法需要枚举完整范围，平方根既不是任务边界，也会引入不必要的浮点判断。

正确性依据​

对任一合数 x，令 p 为其最小质因子，写成 x = p × m。扫描到 m 时，所有小于 p 的质数都不整除 m；内层循环会到达 p 并标记 x。之后若尝试由更大质因子标记同一合数，前一步的整除条件已使循环停止。因此每个合数恰被最小质因子标记一次，未标记的恰为质数。

样例执行过程​

n = 10 时依次发现 2、3、5、7，合数 6 已在处理 3 时由 3 × 2 标记。轮到处理 6，内层先检查到 2 > 10 / 6，因此直接越界停止，不执行乘法和标记操作。最终质数表长度为 4。

代码实现​

C++17
#include <iostream>
#include <vector>

using namespace std;

vector<int> linearSieve(int n) {
    vector<bool> isComposite(n + 1, false);
    vector<int> primes;

    for (int number = 2; number <= n; number++) {
        if (!isComposite[number]) {
            primes.push_back(number);
        }
        for (int prime : primes) {
            if (prime > n / number) {
                break;
            }
            isComposite[prime * number] = true;
            if (number % prime == 0) {
                break;
            }
        }
    }
    return primes;
}

#ifndef ALGORITHM_TUTORIAL_TEST
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    cout << linearSieve(n).size() << '\n';
}
#endif

linearSieve／linear_sieve 返回质数表，入口只输出其长度，保持算法部分可测试、可复用。

复杂度分析​

每个合数仅被标记一次，时间复杂度为 O(n)；合数标记与质数表使用 O(n) 额外空间。

边界与易错点​

  • n = 1 时循环不执行，应返回空表而不是把 1 计入。
  • 内层循环的停止条件是当前 prime 整除 number，不是只在乘积越界时停止。
  • 先检查 prime <= n / number，再标记乘积，避免溢出和越界。

模式迁移​

当后续题需要很多数的最小质因子、欧拉函数或快速分解时，可在筛法过程中增加数组记录信息。若只处理单个整数，试除法反而更节省空间。