如果你也是因为超时问题而来，请跳转至【LeetCode 204. 计数质数】从暴力枚举到打表预处理
题目描述
给定整数 n ，返回所有小于非负整数 n 的质数的数量。
示例 1 输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。 示例 2： 输入：n = 0 输出：0 示例 3： 输入：n = 1 输出：0 提示： 0 <= n <= 5 * 10^6解题思路演进
这道题是经典的数论基础题。根据数据范围 n <= 5 * 10^6，我们可以推导出不同算法的时间复杂度表现。
方法一：暴力枚举（会超时 TLE）
最直观的想法是：遍历从 2 到 n-1 的每一个数字 i，然后判断 i 是否为质数。判断质数的方法是尝试用 2 到 sqrt(i) 之间的数字去整除 i。
代码实现：
class Solution { public: bool isPrime(int x) { for (int i = 2; i * i <= x; i++) { if (x % i == 0) return false; } return true; } int countPrimes(int n) { int ans = 0; for (int i = 2; i < n; i++) { if (isPrime(i)) ans++; } return ans; } };复杂度分析：
- 时间复杂度：O(N根号N)。当N=5×106时，计算量达到十亿级别，在 LeetCode 上必定超时。
- 空间复杂度：O1。
方法二：埃拉托斯特尼筛法（Sieve of Eratosthenes）
既然暴力法会超时，我们需要一种更高效的算法。埃拉托斯特尼筛法（简称埃氏筛）是一种古老且经典的质数筛选算法。
核心思想：
如果 x 是质数，那么 x 的倍数（2x, 3x, 4x...）一定不是质数。我们可以从 2 开始遍历，将当前数字的倍数全部标记为“合数”。遍历结束后，未被标记的数字就是质数。
在实现埃氏筛时，有一个极其重要的优化细节：内层循环从 i * i 开始，而不是 2 * i。
for (int j = i * i; j < n; j += i) { isPrime[j] = false; }为什么可以从 i * i 开始？
假设当前遍历到的质数是 i。对于 i 的倍数 i * k：
- 如果 k < i，那么 i * k 必然已经被比 i 更小的质数（比如 k 的某个质因数）筛选过了。
- 例如：当 i = 5 时，5 * 2 = 10（已被 2 筛掉），5 * 3 = 15（已被 3 筛掉），5 * 4 = 20（已被 2 筛掉）。
- 因此，为了避免重复标记（重复计算），我们从 i * i 开始标记即可，这是 i 的倍数中第一个尚未被更小质数标记的数字。
代码实现 (C++)
class Solution { public: int countPrimes(int n) { // 边界条件：小于等于 2 的数没有质数 if (n <= 2) return 0; // 创建布尔数组，isPrime[i] 表示数字 i 是否为质数 // 初始默认全部为 true (质数) vector<bool> isPrime(n, true); // 0 和 1 不是质数 isPrime[0] = false; isPrime[1] = false; // 从 2 开始筛，只需要遍历到 sqrt(n) 即可 for (int i = 2; i * i < n; i++) { if (isPrime[i]) { // 优化：从 i * i 开始标记，步长为 i for (int j = i * i; j < n; j += i) { isPrime[j] = false; } } } // 统计所有标记为 true 的数字 int count = 0; for (int i = 2; i < n; i++) { if (isPrime[i]) count++; } return count; } };复杂度分析：
- 时间复杂度：ONloglogN。这是埃氏筛的经典复杂度，非常接近于线性时间，对于5×106的数据量可以轻松通过。
- 空间复杂度：ON。需要一个长度为N的布尔数组来记录状态。由于 vector<bool> 在 C++ 中经过了位压缩优化，实际占用内存非常小。
进阶拓展：线性筛（欧拉筛）
虽然埃氏筛已经足够优秀，但在某些极端情况下，可能会提到线性筛（欧拉筛）。
埃氏筛的痛点：一个合数可能会被多个质数重复标记。例如 12，会被 2 标记一次（2 * 6），也会被 3 标记一次（3 * 4），存在冗余计算。
线性筛的核心思想：保证每个合数只会被它的最小质因数筛掉。这样时间复杂度可以降到严格的O(N)。
线性筛代码示例：
class Solution { public: int countPrimes(int n) { vector<int> primes; // 存储已找到的质数 vector<bool> isPrime(n, true); // 标记数组 int ans = 0; for (int i = 2; i < n; i++) { if (isPrime[i]) { primes.push_back(i); ans++; } // 核心：用当前质数 primes[j] 去筛 i * primes[j] for (int j = 0; j < primes.size() && i * primes[j] < n; j++) { isPrime[i * primes[j]] = false; // 保证每个合数只被它的最小质因数筛掉 if (i % primes[j] == 0) break; } } return ans; } };
编程)
