如何高效统计小于 n 的质数个数？（埃氏筛，LeetCode 204）

简化版

统计所有小于 n 的质数的数量。逐个判断每个数是否质数太慢，用埃拉托斯特尼筛法（埃氏筛）：从 2 开始，把每个质数的所有倍数都标记为「非质数」，筛完后没被标记的就是质数。优化点：外层只需筛到 √n，内层从 i*i 开始标记（更小的倍数已被更小的质因子标记过）。时间复杂度 O(n log log n)，接近线性。更优有线性筛（欧拉筛）O(n)。

详细版

int countPrimes(int n) {
    if (n < 3) return 0;                    // 小于 2 没有质数
    boolean[] notPrime = new boolean[n];   // notPrime[i] = i 是否合数
    int count = 0;
    for (int i = 2; i < n; i++) {
        if (!notPrime[i]) {                // i 是质数
            count++;
            // 从 i*i 开始标记 i 的倍数为合数（用 long 防 i*i 溢出）
            for (long j = (long) i * i; j < n; j += i) {
                notPrime[(int) j] = true;
            }
        }
    }
    return count;
}

埃氏筛：遇到质数 i，就把它的倍数全标记为合数。
从 i*i 开始：i*2, i*3, ..., i*(i-1) 这些倍数已被更小的质因子（2,3,…）标记过，从 i*i 起才有新标记。
外层到 √n 即可：大于 √n 的数若是合数，必有 ≤√n 的质因子已把它标记。
复杂度：O(n log log n) 时间、O(n) 空间。

完整版教学

一、朴素法：逐个判断质数

最直接：对 2 到 n-1 每个数，判断它是不是质数（试除 2 到 √x），累计。单个判断 O(√x)，总共约 O(n√n)，n 大时超时。核心矛盾是每个数独立判断有大量重复劳动——比如 12、18、24 都要重新试除 2、3。筛法的思想是反过来：不判断每个数，而是从质数出发主动「划掉」它的倍数，把重复利用起来。

二、埃氏筛：从质数出发划掉倍数

埃拉托斯特尼筛法的过程像「筛沙子」：

假设 2 到 n-1 都是质数（notPrime 全 false）。
从 2 开始，2 是质数 → 把 4、6、8、10… 所有 2 的倍数标记为合数。
下一个没被标记的是 3 → 质数，把 6、9、12… 3 的倍数标记为合数。
4 已被标记（合数），跳过；5 是质数，标记 5 的倍数……
一直筛下去，最后没被标记的就是质数。

核心思想：每个合数都会被它的某个质因子「筛掉」，所以从质数出发标记倍数，能一网打尽所有合数，剩下质数。

三、两个关键优化

① 内层从 i*i 开始，而非 2*i

当处理质数 i 时，它的倍数 2i, 3i, ..., (i-1)i 中，每一个都含有比 i 小的质因子（2、3、…、i-1），早就在处理那些更小质数时被标记过了。所以只有从 i*i 开始的倍数（i*i, i*(i+1), ...）才是「首次被 i 标记」的，前面的重复标记可以跳过，省不少时间。

注意 i*i 可能超过 int 范围，用 long 计算再转回，防溢出。

② 外层只需筛到 √n

如果一个数 x < n 是合数，它必有一个 ≤ √x ≤ √n 的质因子。也就是说，所有合数在外层 i 走到 √n 之前就已经被标记完了。所以外层筛到 √n 即可停止标记（但计数仍要遍历到 n-1）。实现上常把两件事合在一个循环里，靠「从 ii 开始、ii < n」自然终止。

四、复杂度分析

埃氏筛的时间是 O(n log log n)——对每个质数 p，标记它的倍数要 n/p 次操作，所有质数的 n/p 之和 ≈ n × (1/2 + 1/3 + 1/5 + ...)，质数倒数和增长极慢（约 log log n），所以总量接近线性。空间 O(n)（布尔数组）。这比朴素 O(n√n) 快非常多。

五、进阶：线性筛（欧拉筛）O(n)

埃氏筛有个小缺陷：一个合数会被它的多个质因子重复标记（如 12 被 2 和 3 各标记一次）。线性筛（欧拉筛）保证每个合数只被它的「最小质因子」标记一次，达到严格 O(n)。它维护一个已知质数列表，对每个 i 用「i × 每个已知质数」去标记，并在 i % prime == 0 时 break（保证只用最小质因子）。线性筛是竞赛/进阶考点，面试能说清埃氏筛 + 提一句线性筛即可。

六、从 p² 开始筛的完整理由

当处理质数 p 时，小于 p² 的倍数 kp 满足 k<p，它已经在处理更小因子 k（或 k 的质因子）时被筛掉。因此从 p² 开始不会漏掉合数，只会避免重复工作。外层只需处理 p²<n，因为任何小于 n 的合数至少有一个因子不超过其平方根。

统计 n=20 以下质数
p=2：从 4 划掉 4,6,8,...,18
p=3：从 9 划掉 9,12,15,18
p=4 已被标记，跳过
下一候选 p=5 时 p²=25>=20，停止筛倍数
未标记：2,3,5,7,11,13,17,19
答案 8

校验维度	本题必须保持的结论
循环/递推不变量	进入 p 时，所有小于 p 的质因子对应倍数已标记；未标记的 p 必为质数。
边界条件	题目统计严格小于 n；`n<=2` 时答案为 0，数组下标范围是 `[0,n)`。
复杂度与代价	埃氏筛 O(n log log n) 时间 O(n) 空间；`p*p` 应防整数溢出。
自检方式	用最小输入、典型输入和触及边界的输入分别手推，结果应与定义一致。

这组推演的作用不是替代证明，而是把抽象规则落到每一步状态变化上。面试写完代码后，应主动指出不变量如何保证不漏解，以及边界为何不会越界或死循环。若手推结果与定义不一致，应先修正状态语义，而不是继续给代码打补丁。

七、面试现场如何验证这道题

数学题不能只凭样例相信公式，必须同时核对定义域、推导条件和定宽整数边界。本题应先复述这条不变量：进入 p 时，所有小于 p 的质因子对应倍数已标记；未标记的 p 必为质数。只有代码的初始化、更新顺序和终止条件都维持它，样例通过才具有证明力。

典型路径从“统计 n=20 以下质数”开始手推，最后应得到“答案 8”。
边界复核：题目统计严格小于 n；n<=2 时答案为 0，数组下标范围是 [0,n)。
代价复核：埃氏筛 O(n log log n) 时间 O(n) 空间；p*p 应防整数溢出。
用 0、1、最小合法值和最大合法值检查公式的定义域。
乘法、取绝对值或取负前先判断是否可能触及 Integer.MIN_VALUE 等不对称边界。
若算法依赖单调性、抵消或整除关系，要明确题设保证何时成立、何时必须额外验证。

最后要主动构造一个“少写一次循环、改变一个不等号或交换两行更新就会失败”的反例。能说清反例破坏了哪条不变量，比只报出复杂度更能证明真正掌握了算法。

记忆钩子：本题的代码可以压缩，但“进入 p 时，所有小于 p 的质因子对应倍数已标记；未标记的 p 必为质数。”这条正确性主线不能省。

八、常见误区与追问

误区：从 2p 开始才不会漏筛。 从 p² 开始同样完整，较小倍数早已被更小质因子筛过。
误区：1 是质数。 质数定义要求大于 1 且只有 1 和自身两个正因子。
误区：题目要求统计小于等于 n 的质数。 LeetCode 204 是严格小于 n，数组与循环边界不能包含 n。
追问：为什么复杂度不是 O(n log n)？ 只对质数 p 访问约 n/p 个倍数，质数倒数和增长为 log log n。
追问：线性筛为什么是 O(n)？ 它让每个合数只被其最小质因子筛掉一次。
追问：超大范围如何省内存？ 可用位图只存奇数，或采用分段筛分批处理区间。

九、加强记忆

统计质数个数 = 埃氏筛：假设都是质数，从 2 开始，遇到质数就把它的倍数全标记为合数，最后没被标记的即质数。两个关键优化：内层从 i*i 开始（更小的倍数已被更小质因子标记，i*i 用 long 防溢出）、外层筛到 √n（合数必有 ≤√n 的质因子）。时间 O(n log log n)、空间 O(n)。进阶 线性筛（欧拉筛） 让每个合数只被最小质因子标记一次达 O(n)。核心：别逐个判断，从质数出发划掉倍数。

简化版

详细版