素数筛法

素数筛法

埃氏筛法与线性筛法。

概念

素数筛法解决一个问题：给定上限 $n$，批量找出 $1\sim n$ 中哪些是质数。埃氏筛从 $2$ 开始，把每个质数 $p$ 的所有倍数 $p,p^2,p^3,\ldots$ 标记为合数，外层只需遍历到 $\sqrt{n}$。线性筛（欧拉筛）在内层用已求出的质数表 $b[]$，对每个合数 $i\cdot k$ 只被其最小质因子筛一次，保证总复杂度 $O(n)$，并常顺带维护每个数的最小质因子、约数个数等。与 cspj.math.number-theory 的分界：数论叶子考 GCD、因子性质、模运算；本叶子只考筛的代码结构与复杂度——外层循环上界、内层 break 何时触发、a[i*k] 标记含义。目前语料里筛法题集中在 2021 年一篇阅读程序。

CSP-J 常考

• cspj-r1-2021 第 28 题：线性筛 init() 中，若输入不为 $1$，删去第 13 行是否不影响输出（考最小质因子分支与 break）。
• cspj-r1-2021 第 31 题：同一程序，init 的时间复杂度（线性筛为 $O(n)$，不是 $O(n^2)$）。

目前语料只有上述 2 道挂在本叶子的题。

// 埃氏筛：isPrime[i]==true 表示 i 为质数
const int N = 100000;
bool isPrime[N + 1];
void eratosthenes(int n) {
    fill(isPrime, isPrime + n + 1, true);
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= n; ++i)
        if (isPrime[i])
            for (int j = i * i; j <= n; j += i)
                isPrime[j] = false;
}

易错点

• 埃氏筛内层应从 $i*i$ 开始标记，从 $2i$ 开始也能对但重复工作多；外层只需到 $\sqrt{n}$。
• 线性筛里 if (i % k == 0) break 保证每个合数只被最小质因子筛到，删掉或写错会导致重复标记或漏筛。
• 不要把「求 $n$ 的因子平方和」当成筛法——那是枚举因子，属 cspj.math.number-theory。
• 数组下标 $1\sim n$ 时，$0$ 和 $1$ 都不是质数，初始化别漏。