企业官网建设流程全解析

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)。

筛法的核心思想：

1. 准备一个长度为 n 的布尔数组isNotPrime，true表示该下标已被标记为合数（非质数）。
2. 从 2 开始遍历，若当前数 i 尚未被标记为合数，则 i 一定是质数，将其所有大于等于 i² 的倍数j = i*i, i*i+i, i*i+2i, ...全部标记为合数。
3. 遍历结束后，统计 [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×i（k < i），k 必有一个更小的质因子，这些倍数在更早的轮次中已被标记，无需重复。
• 例如 i = 5 时，5×2=10、5×3=15、5×4=20 在 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 两个既非质数也非合数的特殊整数。

复杂度分析

当 n ≤ 2 时，外层循环条件i*i < n与统计循环条件i < n均不成立，函数直接返回 0，边界情形无需额外特判。

单元测试验证：三种规模下的正确性

仓库为本题配套了表驱动测试，见 204. Count Primes_test.go。测试用例覆盖了三种不同数量级的输入：

测试代码采用仓库统一的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 -covermode=atomic -coverprofile=coverage.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：中文版题目与解题思路说明；
• 204. Count Primes.go：可运行的 Go 实现，package leetcode；
• 204. Count Primes_test.go：表驱动单元测试。

从仓库结构看，leetcode/目录下每个题目文件夹统一遵循「题解文档 + README + 实现 + 测试」的四件套约定，website/content.en/ChapterFour/下的英文文档与leetcode/目录按题号一一对应，便于检索与维护。本项目模块名为github.com/halfrost/LeetCode-Go（见 go.mod），Go 版本要求为 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