LeetCode 204. 计数质数

约 5 分钟
文章信息 12 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节 阿里 微软 美团 京东 百度 快手
标签
数组 数学 枚举 数论

题目描述

✅ 204. 计数质数

image-20260928220647226

题意分析

统计非负整数 n 之前有多少个质数，范围是严格小于 n 的所有整数，不包含 n 本身。质数必须大于 1，并且除了 1 和自身没有其他正因数，因此真正需要统计的范围是 [2, n)。

返回的是数量，不需要返回质数列表。n <= 2 时这个范围为空，答案为 0；题目上界较大，逐个数字反复试除会做大量重复工作。

解法：埃氏筛

核心思路

[!blue]

筛法把判断方向反过来：不逐个询问一个数能否被整除，而是从小到大利用已经发现的质数，统一标记它们的倍数为合数。用 composite[x] 表示数字 x 是否已被确认是合数，初始全部为 false。

扫描到 i 时，如果它尚未被标记，就可以把它当作质数。因为一个合数一定含有比自身更小的质因子，处理那个质因子时就会标记它。若 i 已经是合数，它的倍数也能由这些较小质因子负责，不需要重复作为筛选源。

对质数 i，从 i * i 开始标记，每次增加 i。比平方更小的非自身倍数可写为 i * k，其中 2 <= k < i；k 至少含有一个比 i 小的质因子，这个倍数已经被前面的筛选处理。因此跳过这些较小倍数不会漏标，也不会把质数 i 自己划掉。

外层只需处理到平方仍小于 n 的位置。任意合数都可以分成两个大于一的因子，其中至少一个不超过它的平方根，所以一定会被这个范围内的某个质因子筛掉。代码用 i <= (n - 1) / i 表示 i * i < n，先判断合法范围再计算平方。

筛选结束后，在 [2, n) 中统计所有仍未标记的位置即可。零和一虽然同样保持默认值，却不在统计范围内，不会被当成质数。

解题步骤

  1. 若 n <= 2，直接返回 0；否则创建长度为 n 的布尔数组 composite。
  2. 从 i = 2 开始，只要 i <= (n - 1) / i 就继续；已标记为合数的 i 跳过。
  3. 对未标记的 i，从 i * i 起，每次增加 i，将所有小于 n 的对应位置设为 true。
  4. 遍历下标 2 到 n - 1，统计值为 false 的位置并返回数量。

代码实现

class Solution {
    public int countPrimes(int n) {
        if (n <= 2) {
            return 0;
        }

        boolean[] composite = new boolean[n];

        for (int i = 2; i <= (n - 1) / i; i++) {
            if (composite[i]) {
                continue;
            }

            // 更小倍数已被较小质因子标记，从平方开始避免重复工作。
            for (int multiple = i * i; multiple < n; multiple += i) {
                composite[multiple] = true;
            }
        }

        int count = 0;

        for (int i = 2; i < n; i++) {
            if (!composite[i]) {
                count++;
            }
        }

        return count;
    }
}

func countPrimes(n int) int {
    if n <= 2 {
        return 0
    }

    composite := make([]bool, n)
    for i := 2; i <= (n-1)/i; i++ {
        if composite[i] {
            continue
        }
        // 更小倍数已被较小质因子标记，从平方开始避免重复工作。
        for multiple := i * i; multiple < n; multiple += i {
            composite[multiple] = true
        }
    }

    count := 0
    for i := 2; i < n; i++ {
        if !composite[i] {
            count++
        }
    }
    return count
}

复杂度分析

  • 时间复杂度：$O(n\log\log n)$。只有质数作为标记源，质数 p 至多标记约 n / p 个倍数，这些工作量之和为 $O(n\log\log n)$；最后统计还需 $O(n)$。
  • 空间复杂度：$O(n)$，布尔数组记录小于 n 的数是否为合数。

关键点总结

[!green]

  • 从已知质数批量排除合数，避免对每个候选数重复试除。
  • 从平方开始，省去已经由更小质因子处理的倍数。
  • 每个合数都有不超过其平方根的质因子，保证提前结束外层筛选仍能找全合数。
  • 筛选和统计都使用严格小于 n 的右边界，零和一单独排除在统计范围外。

易错点总结

[!yellow]

  • 把零或一也纳入未标记位置的统计，会把非质数算进答案。
  • 使用包含 n 的循环边界，会违背严格小于的要求，并可能访问长度为 n 的数组末尾之外。
  • 从质数本身开始标记，会把真正的质数也筛掉；从平方开始才符合本实现的筛选范围。
  • 内层步长写成一，会把非倍数位置一起标记；步长必须等于当前质数。
  • 把未标记值直接解释成质数，却没有先完成必要的小质因子筛选，会错误保留合数。

相似题目

题目 难度 关联与区别
补充题 153. 整数的质因数分解 简单 试除分解单个数与筛出范围内全部素数任务不同；可先筛小素数，再用于多个数的试除。
补充题 214. 不大于 n 的全部素数 中等 都用筛法标记合数；本题统计质数个数，补充题输出质数列表。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/62404477
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！