LeetCode 题解工作台
计数质数
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。 示例 1： 输入： n = 10 输出： 4 解释： 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。 示例 2： 输入： n = 0 输出： 0 示例 3： 输入： n = 1 输出 ：0 提示： 0 6
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·数学
答案摘要
如果 是质数，那么大于 的 的倍数 ,,… 一定不是质数，因此我们可以从这里入手。 设 表示数 是不是质数，如果是质数则为 ，否则为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
示例 1：
输入：n = 10 输出：4 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0 输出：0
示例 3：
输入：n = 1 输出：0
提示：
0 <= n <= 5 * 106
解题思路
方法一：埃氏筛
如果 是质数，那么大于 的 的倍数 ,,… 一定不是质数，因此我们可以从这里入手。
设 表示数 是不是质数，如果是质数则为 ，否则为 。
我们在 范围内顺序遍历每个数 ，如果这个数为质数（），质数个数增 1，然后将其所有的倍数 都标记为合数（除了该质数本身），即 ，这样在运行结束的时候我们即能知道质数的个数。
时间复杂度 。
class Solution:
def countPrimes(self, n: int) -> int:
primes = [True] * n
ans = 0
for i in range(2, n):
if primes[i]:
ans += 1
for j in range(i + i, n, i):
primes[j] = False
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the sieve: marking multiples up to sqrt(n) yields O(n log log n), while space complexity is O(n) for the boolean array used to track primes. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if you understand the inefficiency of checking all numbers up to n individually.
- question_mark
Wants to see familiarity with array-based prime marking techniques.
- question_mark
Looks for mathematical reasoning to reduce redundant computation, especially using sqrt(n).
常见陷阱
外企场景- error
Attempting to divide every number by all smaller numbers instead of using a sieve.
- error
Not handling n <= 2 edge cases, which can lead to incorrect counts.
- error
Incorrectly marking multiples or starting from 0 or 1 instead of 2.
进阶变体
外企场景- arrow_right_alt
Count primes in a range [m, n) instead of from 0 to n.
- arrow_right_alt
Return a list of prime numbers instead of the count, using the same sieve pattern.
- arrow_right_alt
Modify the sieve to support dynamic updates for multiple queries efficiently.