LeetCode 204. 计数质数

约 4 分钟
文章信息 12 个分类 7 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 微软 美团 阿里巴巴 快手 百度 京东
标签
数组 数学 枚举 数论 筛法 素性测试 素数筛法
目录

题目描述

✅ 204. 计数质数

题意分析

给定一个非负整数 n，要求返回质数的个数。质数指大于 1 且只能被 1 和自身整除的自然数。

第一个必须抠清楚的字眼是「小于 n」。这是一个开区间，统计范围是 2 到 n - 1，n 本身无论是不是质数都不计入。很多人第一遍写完提交后差 1，就是把它当成了闭区间。

第二个信号来自数据范围：n 最大到 5 × 10^6。这个量级明确排斥了「对每个数单独做一次整除判定」的思路，同时又允许开一个长度为 n 的辅助数组，说明出题人期待的是一种「拿空间换时间、把判定结果复用起来」的做法。

边界要单独想清楚：0 和 1 都不是质数，n 取 0、1、2 时答案都是 0，因为此时区间里根本没有大于 1 的数；n = 3 时区间是 {2}，答案是 1。

解法：埃氏筛

核心思路

对每个数单独试除会重复做大量工作。埃氏筛反过来维护“是否为合数”：从 2 开始扫描，若 composite[i] 仍为 false，则 i 是质数，并把它的倍数全部标记为合数。最后统计区间 [2, n) 中未被标记的数。

标记从 i * i 开始，因为 2 * i 到 (i - 1) * i 都含有小于 i 的因子，之前已经被标记。也因此只需处理满足 i * i < n 的 i。

正确性依据：任意合数 x < n 都存在不大于 $\sqrt{x}$ 的质因子 p；扫描到 p 时，x 会作为 p 的倍数被标记。反过来，算法只标记质数的倍数，所以未标记且大于等于 2 的数必为质数。

解题步骤

  1. 若 n <= 2，区间 [2, n) 为空，返回 0。
  2. 创建长度为 n 的布尔数组 composite，下标直接代表数字。
  3. 从 2 开始扫描；已标记的 i 直接跳过，否则从 i * i 起、每次增加 i，标记其倍数。
  4. 遍历 2 到 n - 1，统计未标记的下标。

例如 n = 10：2 标记 4、6、8，3 标记 9，剩余的 2、3、5、7 未被标记，因此答案为 4。

代码实现

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)$。每个质数负责标记自己的倍数，所有标记次数的总量接近线性；末尾统计另需 $O(n)$。
  • 空间复杂度：$O(n)$，用于记录小于 n 的数是否为合数。

关键点总结

  • 题目统计的是严格小于 n 的质数，筛选和统计的右边界都不能包含 n。
  • composite[i] == false 才把 i 当作标记源，避免合数重复筛选。
  • 从 i * i 开始既不漏标，又跳过已经处理过的较小倍数。
  • 用 i <= (n - 1) / i 表达 i * i < n，可避免乘法溢出；若追问严格线性筛法，可再介绍欧拉筛。

易错点总结

  • 0 和 1 不是质数，统计必须从 2 开始。
  • 右边界是 n - 1；写成 <= n 会越界或把 n 错误计入。
  • 内层步长必须是 i，并从 i * i 开始；从 2 * i 开始虽正确，但会做重复工作。
  • 若直接写 i * i < n，在更大的整数范围可能溢出；除法形式更稳妥。

相似题目

题目 难度 考察点
172. 阶乘后的零 中等 质因子 5 的个数
202. 快乐数 简单 数位平方和判环
263. 丑数 简单 反复除尽固定因子
264. 丑数 II 中等 多指针合并递推
786. 第 K 个最小的质数分数 中等 质数表 + 二分答案
1390. 四因数 中等 因数枚举与求和