LeetCode-Go 题解204. Count Primes —— 埃拉托斯特尼筛法统计小于 n 的质数个数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 204 题 Count Primes统计小于非负整数 n 的质数个数展开以开源仓库 LeetCode-Go 中 0204.Count-Primes 题解文档 为主体骨架结合仓库内的 Go 实现与单元测试源码进行纵深剖析。读完本文你将掌握埃拉托斯特尼筛法Sieve of Eratosthenes在 Go 中的典型写法、i*i n起始优化的原理以及如何通过go test验证答案的正确性。题目原文与理解原题要求非常简洁Count the number of prime numbers less than a non-negative number,n.即统计所有小于非负整数 n 的质数的数量注意是严格小于 n不包含 n 本身。原文档给出的示例Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.当 n 10 时小于 10 的质数为 2、3、5、7共 4 个因此输出为 4。仓库在 leetcode/0204.Count-Primes/README.md 中给出了中文版题目大意统计所有小于非负整数 n 的质数的数量。两个版本的题目描述完全一致是理解本题的基线。边界条件分析n 是非负整数因此需要考虑 n 0、1、2 的情形。最小的质数是 2当 n ≤ 2 时小于 n 的范围内不存在任何质数答案恒为 0。判断一个数是否为质数只需要检查从 2 到其平方根范围内的因子即可。这些边界条件会在后文的实现与测试中体现。解题思路埃拉托斯特尼筛法原文档给出的解题思路只有一句话给出一个数字 n要求输出小于 n 的所有素数的个数总和。简单题。虽然题目本身是「简单题」但直接对每个数单独做质数判定时间复杂度会达到 O(n√n)。对于大 n 会非常低效。仓库中的实现采用的是经典的埃拉托斯特尼筛法Sieve of Eratosthenes一趟筛法即可标记出 2, n) 区间内所有的合数时间复杂度为 O(n log log n)空间复杂度为 O(n)。筛法的核心思想准备一个长度为 n 的布尔数组isNotPrimetrue表示该下标已被标记为合数非质数。从 2 开始遍历若当前数 i 尚未被标记为合数则 i 一定是质数将其所有大于等于 i² 的倍数j i*i, i*ii, i*i2i, ...全部标记为合数。遍历结束后统计 [2, n) 区间内仍为false未被标记的下标个数即为质数数量。仓库源码级实现剖析原文档给出了完整的 Go 代码仓库中的实际实现位于 [204. Count Primes.go与文档保持一致package leetcode func countPrimes(n int) int { isNotPrime : make([]bool, n) for i : 2; i*i n; i { if isNotPrime[i] { continue } for j : i * i; j n; j j i { isNotPrime[j] true } } count : 0 for i : 2; i n; i { if !isNotPrime[i] { count } } return count }逐段解读1. 筛法数组初始化isNotPrime : make([]bool, n)数组长度为 n下标恰好覆盖 [0, n) 所有整数。isNotPrime[i] true表示 i 是合数默认false即假定全部为质数再通过筛法逐一排除。下标 0 和 1 不会被任何质数筛到但由于统计时从 2 开始计数它们不会干扰结果。2. 外层循环遍历潜在质因子for i : 2; i*i n; i {从 2 开始终止条件为i*i n即 i √n。依据是数论基本性质若合数 m 存在小于 m 的因子则必有一个因子不超过 √m。因此合数在 [2, n) 区间内的最小质因子一定小于 √n只要筛掉这些质因子的倍数就能覆盖区间内全部合数。若isNotPrime[i]已为true说明 i 是某个更小质数的倍数其倍数早已被标记直接continue跳过避免重复标记。3. 内层循环从 i² 开始标记倍数for j : i * i; j n; j j i { isNotPrime[j] true }倍数从i²开始而非 i×2。原因对于小于 i 的倍数 k×ik ik 必有一个更小的质因子这些倍数在更早的轮次中已被标记无需重复。例如 i 5 时5×210、5×315、5×420 在 i 2、3 的轮次中已被标记直接从 25 开始即可。这一优化将筛法的总工作量降至约 n·ln(ln n)并避免了大量重复赋值。4. 统计阶段count : 0 for i : 2; i n; i { if !isNotPrime[i] { count } }再次遍历 [2, n)凡isNotPrime[i]仍为false的下标即为质数。从 2 开始遍历天然排除了 0、1 两个既非质数也非合数的特殊整数。复杂度分析指标数值说明时间复杂度O(n log log n)埃拉托斯特尼筛法的经典复杂度空间复杂度O(n)长度为 n 的布尔数组当 n ≤ 2 时外层循环条件i*i n与统计循环条件i n均不成立函数直接返回 0边界情形无需额外特判。单元测试验证三种规模下的正确性仓库为本题配套了表驱动测试见 204. Count Primes_test.go。测试用例覆盖了三种不同数量级的输入输入 n期望输出说明104质数为 2、3、5、7即题目原始示例10025小于 100 的质数共 25 个1000168小于 1000 的质数共 168 个测试代码采用仓库统一的para204 / ans204结构体约定type para204 struct { one int } type ans204 struct { one int }Test_Problem204通过表驱动方式依次对每个用例调用countPrimes并在终端输出【input】与【output】便于人工核对。如何运行测试从仓库根目录执行go test ./leetcode/0204.Count-Primes/ -v -run Test_Problem204运行后可以看到如下形式的输出------------------------Leetcode Problem 204------------------------ 【input】:10 【output】:4 【input】:100 【output】:25 【input】:1000 【output】:168三个用例全部通过说明实现与期望答案一致。若想验证全仓库覆盖率仓库根目录的 gotest.sh 提供了统一入口go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本对./leetcode/...下所有题解包执行带覆盖率收集的测试生成的coverage.txt正是仓库宣称「100% test coverage」的数据来源。从源码结构看本仓库的题解组织方式本题解属于 LeetCode-Go 仓库的标准题解单元其目录结构可以归纳如下0204.Count-Primes 题解文档英文题解主体包含 Problem、Problem Summary、Solution Approach、Code 四个小节leetcode/0204.Count-Primes/README.md中文版题目与解题思路说明Count Primes.go可运行的 Go 实现package leetcodeCount Primes_test.go表驱动单元测试。从仓库结构看leetcode/目录下每个题目文件夹统一遵循「题解文档 README 实现 测试」的四件套约定website/content.en/ChapterFour/下的英文文档与leetcode/目录按题号一一对应便于检索与维护。本项目模块名为github.com/halfrost/LeetCode-Go见 go.modGo 版本要求为 1.19实现与测试均可在该环境直接编译运行。复杂度对比与可选优化方向直接试除法不推荐仅作对比朴素做法是对每个候选数逐个尝试除以 2 到 √i 的所有整数func isPrime(x int) bool { if x 2 { return false } for i : 2; i*i x; i { if x%i 0 { return false } } return true }每个数判定的复杂度为 O(√n)n 个数合计 O(n√n)。当 n 达到 10⁶ 量级时其开销远高于筛法的 O(n log log n)因此大规模输入下应优先选择筛法。内存可优化点本实现的isNotPrime为[]bool每个元素占用 1 字节。若 n 极大可考虑使用位图bitmap压缩存储将空间占用降低为原来的 1/8也可利用「偶数除 2 外均为合数」的性质只对奇数建筛进一步减半数组长度。这些属于工程上的进一步优化本仓库实现保持最简洁直观的形态。小结通过本文我们完整梳理了 LeetCode 204 Count Primes 的题目语义、埃拉托斯特尼筛法的原理与实现、i*i起始标记的优化依据以及仓库中表驱动测试的验证方式。核心要点回顾统计范围是严格小于 n 的质数n ≤ 2 时答案为 0筛法仅需遍历到 √n内层从 i² 开始标记倍数即可覆盖全部合数时间复杂度 O(n log log n)、空间复杂度 O(n)是求解本类问题的标准方案仓库的 204. Count Primes.go 实现与原文档代码完全一致并通过 测试用例 在 n 10、100、1000 三档输入下验证正确。掌握本题后你可以将此筛法思路迁移到诸如「区间内质数个数」「质数判定前置预处理」等更复杂的数论问题中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode-Go 题解：204. Count Primes —— 埃拉托斯特尼筛法统计小于 n 的质数个数
LeetCode-Go 题解204. Count Primes —— 埃拉托斯特尼筛法统计小于 n 的质数个数【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文围绕 LeetCode 第 204 题 Count Primes统计小于非负整数 n 的质数个数展开以开源仓库 LeetCode-Go 中 0204.Count-Primes 题解文档 为主体骨架结合仓库内的 Go 实现与单元测试源码进行纵深剖析。读完本文你将掌握埃拉托斯特尼筛法Sieve of Eratosthenes在 Go 中的典型写法、i*i n起始优化的原理以及如何通过go test验证答案的正确性。题目原文与理解原题要求非常简洁Count the number of prime numbers less than a non-negative number,n.即统计所有小于非负整数 n 的质数的数量注意是严格小于 n不包含 n 本身。原文档给出的示例Input: 10 Output: 4 Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.当 n 10 时小于 10 的质数为 2、3、5、7共 4 个因此输出为 4。仓库在 leetcode/0204.Count-Primes/README.md 中给出了中文版题目大意统计所有小于非负整数 n 的质数的数量。两个版本的题目描述完全一致是理解本题的基线。边界条件分析n 是非负整数因此需要考虑 n 0、1、2 的情形。最小的质数是 2当 n ≤ 2 时小于 n 的范围内不存在任何质数答案恒为 0。判断一个数是否为质数只需要检查从 2 到其平方根范围内的因子即可。这些边界条件会在后文的实现与测试中体现。解题思路埃拉托斯特尼筛法原文档给出的解题思路只有一句话给出一个数字 n要求输出小于 n 的所有素数的个数总和。简单题。虽然题目本身是「简单题」但直接对每个数单独做质数判定时间复杂度会达到 O(n√n)。对于大 n 会非常低效。仓库中的实现采用的是经典的埃拉托斯特尼筛法Sieve of Eratosthenes一趟筛法即可标记出 2, n) 区间内所有的合数时间复杂度为 O(n log log n)空间复杂度为 O(n)。筛法的核心思想准备一个长度为 n 的布尔数组isNotPrimetrue表示该下标已被标记为合数非质数。从 2 开始遍历若当前数 i 尚未被标记为合数则 i 一定是质数将其所有大于等于 i² 的倍数j i*i, i*ii, i*i2i, ...全部标记为合数。遍历结束后统计 [2, n) 区间内仍为false未被标记的下标个数即为质数数量。仓库源码级实现剖析原文档给出了完整的 Go 代码仓库中的实际实现位于 [204. Count Primes.go与文档保持一致package leetcode func countPrimes(n int) int { isNotPrime : make([]bool, n) for i : 2; i*i n; i { if isNotPrime[i] { continue } for j : i * i; j n; j j i { isNotPrime[j] true } } count : 0 for i : 2; i n; i { if !isNotPrime[i] { count } } return count }逐段解读1. 筛法数组初始化isNotPrime : make([]bool, n)数组长度为 n下标恰好覆盖 [0, n) 所有整数。isNotPrime[i] true表示 i 是合数默认false即假定全部为质数再通过筛法逐一排除。下标 0 和 1 不会被任何质数筛到但由于统计时从 2 开始计数它们不会干扰结果。2. 外层循环遍历潜在质因子for i : 2; i*i n; i {从 2 开始终止条件为i*i n即 i √n。依据是数论基本性质若合数 m 存在小于 m 的因子则必有一个因子不超过 √m。因此合数在 [2, n) 区间内的最小质因子一定小于 √n只要筛掉这些质因子的倍数就能覆盖区间内全部合数。若isNotPrime[i]已为true说明 i 是某个更小质数的倍数其倍数早已被标记直接continue跳过避免重复标记。3. 内层循环从 i² 开始标记倍数for j : i * i; j n; j j i { isNotPrime[j] true }倍数从i²开始而非 i×2。原因对于小于 i 的倍数 k×ik ik 必有一个更小的质因子这些倍数在更早的轮次中已被标记无需重复。例如 i 5 时5×210、5×315、5×420 在 i 2、3 的轮次中已被标记直接从 25 开始即可。这一优化将筛法的总工作量降至约 n·ln(ln n)并避免了大量重复赋值。4. 统计阶段count : 0 for i : 2; i n; i { if !isNotPrime[i] { count } }再次遍历 [2, n)凡isNotPrime[i]仍为false的下标即为质数。从 2 开始遍历天然排除了 0、1 两个既非质数也非合数的特殊整数。复杂度分析指标数值说明时间复杂度O(n log log n)埃拉托斯特尼筛法的经典复杂度空间复杂度O(n)长度为 n 的布尔数组当 n ≤ 2 时外层循环条件i*i n与统计循环条件i n均不成立函数直接返回 0边界情形无需额外特判。单元测试验证三种规模下的正确性仓库为本题配套了表驱动测试见 204. Count Primes_test.go。测试用例覆盖了三种不同数量级的输入输入 n期望输出说明104质数为 2、3、5、7即题目原始示例10025小于 100 的质数共 25 个1000168小于 1000 的质数共 168 个测试代码采用仓库统一的para204 / ans204结构体约定type para204 struct { one int } type ans204 struct { one int }Test_Problem204通过表驱动方式依次对每个用例调用countPrimes并在终端输出【input】与【output】便于人工核对。如何运行测试从仓库根目录执行go test ./leetcode/0204.Count-Primes/ -v -run Test_Problem204运行后可以看到如下形式的输出------------------------Leetcode Problem 204------------------------ 【input】:10 【output】:4 【input】:100 【output】:25 【input】:1000 【output】:168三个用例全部通过说明实现与期望答案一致。若想验证全仓库覆盖率仓库根目录的 gotest.sh 提供了统一入口go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...该脚本对./leetcode/...下所有题解包执行带覆盖率收集的测试生成的coverage.txt正是仓库宣称「100% test coverage」的数据来源。从源码结构看本仓库的题解组织方式本题解属于 LeetCode-Go 仓库的标准题解单元其目录结构可以归纳如下0204.Count-Primes 题解文档英文题解主体包含 Problem、Problem Summary、Solution Approach、Code 四个小节leetcode/0204.Count-Primes/README.md中文版题目与解题思路说明Count Primes.go可运行的 Go 实现package leetcodeCount Primes_test.go表驱动单元测试。从仓库结构看leetcode/目录下每个题目文件夹统一遵循「题解文档 README 实现 测试」的四件套约定website/content.en/ChapterFour/下的英文文档与leetcode/目录按题号一一对应便于检索与维护。本项目模块名为github.com/halfrost/LeetCode-Go见 go.modGo 版本要求为 1.19实现与测试均可在该环境直接编译运行。复杂度对比与可选优化方向直接试除法不推荐仅作对比朴素做法是对每个候选数逐个尝试除以 2 到 √i 的所有整数func isPrime(x int) bool { if x 2 { return false } for i : 2; i*i x; i { if x%i 0 { return false } } return true }每个数判定的复杂度为 O(√n)n 个数合计 O(n√n)。当 n 达到 10⁶ 量级时其开销远高于筛法的 O(n log log n)因此大规模输入下应优先选择筛法。内存可优化点本实现的isNotPrime为[]bool每个元素占用 1 字节。若 n 极大可考虑使用位图bitmap压缩存储将空间占用降低为原来的 1/8也可利用「偶数除 2 外均为合数」的性质只对奇数建筛进一步减半数组长度。这些属于工程上的进一步优化本仓库实现保持最简洁直观的形态。小结通过本文我们完整梳理了 LeetCode 204 Count Primes 的题目语义、埃拉托斯特尼筛法的原理与实现、i*i起始标记的优化依据以及仓库中表驱动测试的验证方式。核心要点回顾统计范围是严格小于 n 的质数n ≤ 2 时答案为 0筛法仅需遍历到 √n内层从 i² 开始标记倍数即可覆盖全部合数时间复杂度 O(n log log n)、空间复杂度 O(n)是求解本类问题的标准方案仓库的 204. Count Primes.go 实现与原文档代码完全一致并通过 测试用例 在 n 10、100、1000 三档输入下验证正确。掌握本题后你可以将此筛法思路迁移到诸如「区间内质数个数」「质数判定前置预处理」等更复杂的数论问题中。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考