0204. Count Primes
==================
题目信息
--------
:题号: 0204. 计数质数
:难度: Medium
:主题: 数论、质数、埃拉托斯特尼筛法
:原题: `LeetCode 0204 `_
:重点: 统计严格小于 n 的质数,用一个质数一次性排除它的全部倍数
题目重述
--------
给定非负整数 ``n``,返回严格小于 ``n`` 的质数数量。质数是大于 ``1`` 且只有 ``1`` 和自身
两个正因数的整数;``0``、``1`` 都不是质数。统计范围是半开区间 ``[0, n)``,所以即使
``n`` 本身是质数,也不能计入答案。
输入满足 ``0 <= n <= 5 * 10^6``。函数只返回数量,不需要返回质数列表,也不修改输入。
自建示例
--------
上界本身不参与统计:
.. code-block:: text
输入:n = 12
输出:5
解释:2、3、5、7、11 小于 12;12 不在统计范围内。
最小的非零答案:
.. code-block:: text
输入:n = 3
输出:1
解释:严格小于 3 的质数只有 2。
空范围和只有非质数的范围:
.. code-block:: text
输入:n = 0 或 n = 2
输出:0
C++ 实现
--------
.. code-block:: cpp
#include
class Solution {
public:
int countPrimes(int n) {
return countBySieve(n);
}
private:
bool isPrimeByTrialDivision(int value) {
if (value < 2) return false;
for (int factor = 2; factor <= (value - 1) / factor; ++factor) {
if (value % factor == 0) return false;
}
return true;
}
int countByTrialDivision(int n) {
int count = 0;
for (int value = 2; value < n; ++value) {
if (isPrimeByTrialDivision(value)) ++count;
}
return count;
}
int countBySieve(int n) {
if (n <= 2) return 0;
std::vector composite(n, false);
composite[0] = composite[1] = true;
for (int prime = 2; prime <= (n - 1) / prime; ++prime) {
if (composite[prime]) continue;
for (long long multiple = 1LL * prime * prime;
multiple < n;
multiple += prime) {
composite[static_cast(multiple)] = true;
}
}
int count = 0;
for (int value = 2; value < n; ++value) {
if (!composite[value]) ++count;
}
return count;
}
};
题解
----
逐个判质数的直接搜索
~~~~~~~~~~~~~~~~~~~~~~
最直接的办法把每个候选 ``value`` 单独判断:尝试用 ``2`` 到
``sqrt(value)`` 的整数去除它,只要找到一个因数就判定为合数;若一直没有整除,才是质数。
``countByTrialDivision`` 正是这条基线。只检查到平方根是安全的,因为若 ``value = a*b``,
两个因子不可能都大于 ``sqrt(value)``。
这条方法对单个数没有多余判断,但对整个范围重复使用了相同信息。例如知道 2 是质数后,
``4、6、8、10`` 等所有偶数都已经可以一次排除,试除法却仍会分别检查它们。若对每个候选
独立试除,时间约为 ``O(n sqrt(n))``,大量工作来自重复确认“这是某个已知质数的倍数”。
筛法把一次因数发现扩散到所有倍数
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
把 ``0..n-1`` 的每个整数当作一个索引,维护 ``composite[x]`` 表示 ``x`` 是否已经被证明为
合数。扫描到候选 ``prime`` 时:
* 若它已经标记,它是某个更小质数的倍数,不需要再次负责排除倍数;
* 若它未标记,它就是质数;
* 用这个质数把范围内所有倍数标记为合数。
这一次不再对每个候选重新寻找因数,而是让一个已确认质数的知识复用于整列倍数。扫描结束后,
仍未标记的 ``2..n-1`` 索引正是质数,最后只需计数。
为什么从 ``prime * prime`` 开始
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
``prime`` 的 ``2 * prime``、``3 * prime`` 等较小倍数不会漏掉,但会重复工作。设某个倍数为
``prime * factor`` 且 ``factor < prime``;``factor`` 若大于 1,至少有一个质因子不超过
``factor``,这个更小质因子在此前扫描时已经标记了该倍数。
因此 ``prime`` 可能第一次负责的最小倍数是 ``prime * prime``。从这里开始按步长 ``prime``,
既不漏掉需要标记的合数,又跳过了已由更小质因子处理过的前缀。
为什么外层只需到平方根
~~~~~~~~~~~~~~~~~~~~~~~~
若 ``x < n`` 是合数,令 ``prime`` 为它的最小质因子,则
``prime * prime <= x < n``。所以每个合数都能在某个 ``prime`` 满足
``prime * prime < n`` 时被标记;更大的候选不可能是某个尚未发现合数因子的必要起点。
代码使用 ``prime <= (n - 1) / prime`` 表达 ``prime * prime <= n - 1``,避免先计算平方。内层
倍数使用 ``long long``,让“先算平方再比较 ``n``”的中间乘法也有明确的宽度。
筛数组不变量
~~~~~~~~~~~~
外层准备处理 ``prime`` 时保持:
* 已标记的索引确实都有一个因子,质数不会被错误标记;
* 小于 ``prime * prime`` 的合数已经被某个更小质数处理;
* ``composite[0]``、``composite[1]`` 始终为真,不参与最终计数;
* 尚未标记且大于等于 2 的 ``prime`` 没有更小质因子,因此可以作为新的筛因子。
若当前 ``prime`` 已标记,直接跳过不会丢失工作,因为标记它的更小质因子也已经覆盖了它的
倍数。若未标记,从平方开始标记的每个数都含有因子 ``prime``,所以只会删除合数;结合每个
合数的最小质因子界限,循环结束后没有合数残留。
状态走读
~~~~~~~~
以 ``n = 20`` 为例,数组索引只到 19:
.. list-table::
:header-rows: 1
* - 候选 prime
- 动作
- 新增标记
* - 2
- 从 4 开始每隔 2 标记
- 4、6、8、10、12、14、16、18
* - 3
- 从 9 开始每隔 3 标记
- 9、15(12、18 已被标记)
* - 4
- 已标记,跳过
- 无
* - 5
- ``5 * 5 >= 20``,外层停止
- 无
最后未标记的 ``2、3、5、7、11、13、17、19`` 共 8 个。注意 ``20`` 从未作为数组中的候选,
这正是严格小于 ``n`` 的边界。
代码分析
~~~~~~~~
公共入口调用 ``countBySieve``;``countByTrialDivision`` 和它的辅助函数保留为对照,展示从
“每个候选独立找因数”到“一个质数批量删除倍数”的工作变化。
``n <= 2`` 的分支先处理空范围,避免在不存在有效候选时访问筛数组。``composite`` 的下标与
整数值直接对应,因此 ``composite[0]``、``composite[1]`` 的初始化表达了题目的非质数定义。
外层遇到已标记候选就跳过;未标记候选从平方开始,内层每次只增加一个质数步长。
最终循环重新扫描 ``2..n-1`` 并统计未标记项。筛数组保存的是“是否合数”的证明,不是质数列表;
因此结果只需一个计数器,输入 ``n`` 也保持不变。
复杂度与边界
~~~~~~~~~~~~
试除基线对每个候选重复检查因子,时间约为 ``O(n sqrt(n))``,额外空间 ``O(1)``。埃氏筛的
总标记量是各质数倒数之和,时间复杂度为 ``O(n log log n)``,最后的计数扫描为 ``O(n)``,
不改变总量级;筛数组占用 ``O(n)`` 空间。
``n = 0``、``1``、``2`` 时严格小于 ``n`` 的范围没有质数,直接返回 0。``n`` 本身即使是质数
也不进入数组索引;外层平方条件和内层 ``multiple < n`` 共同保持半开区间边界。输入上界使
筛数组规模可控,代码不修改调用者数据。