LeetCode｜Day21｜204. 计数质数｜Python刷题笔记
LeetCode｜Day21｜204. 计数质数｜Python刷题笔记
🗓️ 本文属于【LeetCode 简单题百日计划】系列
👉 点击查看系列总目录 >>
📌 题目简介
题号：204. 计数质数
难度：简单
题目链接：点击跳转
🧾 题目描述（简要）
统计所有小于非负整数 n 的质数的数量。
示例：
输入：n = 10
输出：4
解释：小于 10 的质数有 2, 3, 5, 7，共 4 个。
💡 解法：埃拉托色尼筛法（Sieve of Eratosthenes）
class Solution:def countPrimes(self, n: int) -> int:if n < 2:return 0is_prime = [True] * nis_prime[0] = is_prime[1] = Falsefor i in range(2, int(n ** 0.5) + 1):if is_prime[i]:for j in range(i * i, n, i):is_prime[j] = Falsereturn sum(is_prime)
🧠 我的理解
- 从 2 开始筛选，每次将其倍数标记为非质数；
- 用布尔数组记录每个数是否为质数；
- 外层从 2~√n，内层从 i² 开始标记；
- 时间复杂度 O(n log log n)，非常高效的经典算法。
📌 基础语法复习：
int(n ** 0.5)：取平方根；sum(is_prime)：统计布尔列表中 True 的个数；- 嵌套循环 + 素数筛选是算法基础知识。