详细方法分享可以跳转至【LeetCode 204. 计数质数】从暴力枚举到埃拉托斯特尼筛法题目简述题目链接LeetCode 204. 计数质数 (Count Primes)题目描述给定整数n返回所有小于非负整数n的质数的数量。示例输入n 10 输出4 解释小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。数据范围限制0 n 5 * 10^6算法思路演进针对该题常见的解题思路有三种其时间复杂度与适用场景各有不同。1. 暴力枚举法原理遍历2到n-1的每个数字并逐一判断其是否为质数试除法。复杂度时间复杂度为 O(N根号N)。在 N5×10六次方的数据量下计算量过大会导致超时TLE。2. 埃拉托斯特尼筛法埃氏筛原理从2开始遍历若当前数字为质数则将其所有的倍数标记为合数。遍历结束后未被标记的数字即为质数。核心优化内层循环从i * i开始标记。因为小于i * i的倍数已经被更小的质数筛除过无需重复标记。复杂度时间复杂度为 O(Nlog⁡log⁡N)空间复杂度为 O(N)。足以应对本题的数据规模。3. 线性筛欧拉筛原理在埃氏筛的基础上改进保证每个合数只会被它的最小质因数筛除。复杂度时间复杂度为严格的 O(N)。但由于其内部包含频繁的取模运算和动态数组操作常数项开销较大。在本题 5×10六次方 的数据量下实际运行效率未必优于埃氏筛。性能优化实践在解决本题时算法的理论复杂度并非唯一指标底层代码的实现细节对实际执行效率有决定性影响。以下是实践中容易遇到的性能瓶颈vectorbool的底层开销C 对vectorbool进行了特化采用位压缩1 bit存储数据以节省内存。但这导致每次读写都需要进行位运算在处理大量数据时会显著增加 CPU 开销。优化建议可改用vectorchar或原生数组。除法与溢出判断为防止i * i溢出常见的写法是i n / i。但在 C 中整数除法的指令周期远高于乘法。优化建议使用(long long)i * i n利用 64 位乘法直接判断同时避免溢出与除法开销。CPU 缓存未命中使用时间戳Timestamp机制时若采用int数组4字节替代位压缩数组会导致内存占用激增约 20MB。当数据量超过 CPU 缓存大小时频繁的内存访问会大幅拖慢执行速度。优化建议使用内存占用更小的数据结构如vectorbool提升缓存命中率。无效的边界遍历外层循环遍历整个 NN 会造成不必要的计算。优化建议外层循环只需遍历到 NN​ 即可筛除所有合数。正确代码实现以下提供三种正确的代码方案按推荐度排序。方案一预处理前缀和打表法适用场景数据范围固定且函数会被高频调用。核心思想空间换时间。在程序启动时全局静态初始化一次性计算出所有范围内的质数前缀和。之后函数调用只需 O(1) 的时间查表即可。// 1. 定义全局数组大小开到题目上限 5 * 10^6 5 bool isPrime[5000005]; int prefix[5000005]; // prefix[i] 表示小于 i 的质数个数 // 2. 利用静态变量初始化在程序启动时执行一次 int init []() { for (int i 2; i 5000000; i) isPrime[i] true; // 标准埃氏筛 for (int i 2; (long long)i * i 5000000; i) { if (isPrime[i]) { for (long long j (long long)i * i; j 5000000; j i) { isPrime[j] false; } } } // 计算前缀和 for (int i 1; i 5000000; i) { if (isPrime[i]) prefix[i 1] prefix[i] 1; else prefix[i 1] prefix[i]; } return 0; }(); class Solution { public: int countPrimes(int n) { // 3. O(1) 查表返回 return prefix[n]; } };方案二优化的埃氏筛面试标准解法适用场景常规算法面试考察算法思维。核心思想vectorbool节省内存 外层遍历至 根号n​ 统计阶段完整遍历。class Solution { public: int countPrimes(int n) { if (n 2) return 0; // 使用 vectorbool 进行位压缩节省内存 vectorbool isPrime(n, true); // 核心优化外层循环只遍历到 sqrt(n) for (int i 2; (long long)i * i n; i) { if (isPrime[i]) { // 从 i * i 开始筛步长为 i for (long long j (long long)i * i; j n; j i) { isPrime[j] false; } } } // 完整遍历一次数组统计质数个数不可省略 int ans 0; for (int i 2; i n; i) { if (isPrime[i]) ans; } return ans; } };关键优化代码片段跳过偶数int ans 1; // 2 是质数 for (int i 3; i n; i 2) { // 外层只遍历奇数 if (isPrime[i]) { ans; if ((long long)i * i n) { for (long long j (long long)i * i; j n; j 2 * i) { // 内层只标记奇数 isPrime[j] false; } } } }优化后的代码class Solution { public: int countPrimes(int n) { // 0, 1, 2 的情况 if (n 2) return 0; // 使用 vectorboolC 底层会自动进行位压缩内存占用极小缓存极度友好 vectorbool isPrime(n, true); int ans 1; for (int i 3; i n; i 2) { if (isPrime[i]) { ans; if (i n / i) continue; for (int j i * i; j n; j 2 * i) { isPrime[j] false; } } } return ans; } };方案三线性筛欧拉筛会TLE适用场景明确要求 O(N)时间复杂度。核心思想保证每个合数只被其最小质因数筛除。class Solution { public: int countPrimes(int n) { if (n 2) return 0; 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() (long long)i * primes[j] n; j) { isPrime[i * primes[j]] false; // 保证每个合数只被它的最小质因数筛掉 if (i % primes[j] 0) break; } } return ans; } };