【LeetCode 204. 计数质数】从暴力枚举到埃拉托斯特尼筛法-北京尧图网络

如果你也是因为超时问题而来请跳转至【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; } };

【LeetCode 204. 计数质数】从暴力枚举到埃拉托斯特尼筛法

相关推荐

AI测试效率翻倍：25个Skill拆解测试工作流实战

Magenta 数据集构建指南：用 convert_dir_to_note_sequences 将 MIDI/MusicXML/ABC 批量转换为 NoteSequence TFRecord

智能家居品牌方交付组织的系统架构设计：从人力调度到交付确定性基础设施

更多资讯

openrig开放式铝型材机架DIY全攻略：选型、组装与散热实践

Univer表格SDK实战：插件架构、Canvas渲染与单元格权限控制

LLM推理性能优化：硬件加速器选型与部署实战指南

酒店评论中文情感分析实战：基于Word2Vec与SVM的完整流程

AI资讯日更工作流：轻量高信噪比信号捕获系统

Hyper-V 安装 Linux 服务器：网络桥接、增强功能与时间同步实战

今日更新

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？