如果你也是因为超时问题而来请跳转至【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​)。当N5×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 (质数) vectorbool 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的布尔数组来记录状态。由于 vectorbool 在 C 中经过了位压缩优化实际占用内存非常小。进阶拓展线性筛欧拉筛虽然埃氏筛已经足够优秀但在某些极端情况下可能会提到线性筛欧拉筛。埃氏筛的痛点一个合数可能会被多个质数重复标记。例如 12会被 2 标记一次2 * 6也会被 3 标记一次3 * 4存在冗余计算。线性筛的核心思想保证每个合数只会被它的最小质因数筛掉。这样时间复杂度可以降到严格的O(N)。线性筛代码示例class Solution { public: int countPrimes(int n) { vectorint primes; // 存储已找到的质数 vectorbool 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; } };