LeetCode 204中等数学
计数质数 图解题解
这道题到底在问什么
给一个整数 n,统计所有严格小于 n 的质数的个数。质数 = 只能被 1 和自己整除、且大于 1 的数。
- n
- 10
- 输出
- 4
- 解释
- 小于 10 的质数:2、3、5、7
最优解：一步一步想明白
- 3合数 = 某个质数的倍数。把 2 的倍数、3 的倍数、5 的倍数…… 全划掉,剩下的格子就是质数。这就是筛法。
- 4n = 30,先划掉 0 和 1绿色 = 暂时当成质数,灰色 = 已划掉。0 和 1 先划掉,剩下 2~29 都先当质数候选。
- 52 还活着 → 确认质数从 2 开始扫。2 还活着,所以它是质数。接着把 2 的倍数(4、6、8…)一个个划掉。
- 6划掉 42 确认为质数(绿)。从 2×2=4 起划:4 被划掉。
- 7划掉 6往后跳 2 格:6 划掉(刚划的 4 变灰)。
- 8划掉 8再跳一步:8 划掉。第一行的偶数清完。
- 9划掉 10进第二行,继续每隔 2 格划一个:10 划掉。
- 10划掉 12、14接着划 12、14。
- 11划掉 16再隔 2 格:16 划掉。
- 12划掉 18再划 18。第二行的偶数也清完了。
- 13划掉 20、22进第三行,继续划 20、22。
- 14划掉 24、26、28再划 24、26、28。2 的倍数清完——所有偶数都没了。
- 15比 p×p 小的倍数(像 2p)早被更小的质数划过了。划 3 的倍数时,6=2×3 已被 2 划掉,直接从 9=3×3 起步。
- 163 没被划掉 → 质数扫到 3,它还活着(2 的倍数里没有 3),所以 3 也是质数。轮到用 3 划倍数。
- 17从 9=3×3 起,划掉 93 确认为质数(绿)。从 3×3=9 起划:9 被划掉(6 早被 2 划过,跳过它)。
- 18跳过 12,划掉 15每隔 3 往后:12 早被 2 划过(灰,跳过),15 划掉。
- 19再划 21、27继续每隔 3 划:21、27 划掉(18、24 早被 2 划过)。3 的倍数清完。
- 204 被划过 → 跳过扫到 4,但它早被 2 划掉了(灰)。合数直接跳过,不用拿它去划倍数。
- 215 没被划掉 → 质数扫到 5,它还活着,是质数。从 5×5=25 起划倍数。
- 22从 25=5×5 起,划掉 255 确认为质数(绿)。从 25 起划:25 划掉(10、15、20 早被 2、3 划过)。
- 23n=30 时 5×5=25<30 还要看,下一个质数 7 的 7×7=49 已 ≥30,不必再筛——大于 √n 的合数,小因子早被处理过了。剩下的全是质数。
- 24存活的全是质数 → 共 10 个筛完!绿色的 2、3、5、7、11、13、17、19、23、29 就是小于 30 的全部质数,共 10 个。
- 28n=10 时只到下标 9n=10 时表只到下标 9,绿色质数是 2、3、5、7 共 4 个。表压根不存 10——前提是表长开成 n 而不是 n+1。
⚠️ 容易写错的地方
✗ 错：把 n 自己也算进去
✓ 对：只数严格小于 n 的,表开 [0, n-1]
题目要的是 < n,把 n 算进去会多数一个
✗ 错：内层从 2*i 开始划
✓ 对：从 i*i 开始划
小于 i*i 的倍数早被更小质数划过,从 2i 起是白做(也不算错,只是慢)
✗ 错：i*i 用 int 直接乘
✓ 对：C++/Java 用 long 防溢出
n 很大时 i*i 可能超过 int 上限,溢出成负数导致条件失效
完整代码（Python / C++ / Java）
Python
class Solution:
def countPrimes(self, n):
if n < 3:
return 0 # 小于3没有质数<n
is_prime = [True] * n # 先全当质数
is_prime[0] = is_prime[1] = False # 0、1 不是质数
i = 2
while i * i < n: # 筛到 √n 即可
if is_prime[i]: # i 还活着 → 是质数
for j in range(i * i, n, i): # 从 i*i 起划倍数
is_prime[j] = False
i += 1
return sum(is_prime) # 数还剩多少 TrueC++
class Solution {
public:
int countPrimes(int n) {
if (n < 3) return 0;
vector<bool> isPrime(n, true); // 先全当质数
isPrime[0] = isPrime[1] = false; // 0、1 不是质数
for (int i = 2; (long long)i * i < n; i++) {
if (isPrime[i]) { // i 还活着
for (int j = i * i; j < n; j += i)
isPrime[j] = false; // 划掉倍数
}
}
int cnt = 0;
for (int k = 2; k < n; k++) if (isPrime[k]) cnt++;
return cnt;
}
};Java
class Solution {
public int countPrimes(int n) {
if (n < 3) return 0;
boolean[] isPrime = new boolean[n]; // 默认 false
Arrays.fill(isPrime, true); // 先全当质数
isPrime[0] = false; isPrime[1] = false;
for (int i = 2; (long) i * i < n; i++) {
if (isPrime[i]) { // i 还活着
for (int j = i * i; j < n; j += i)
isPrime[j] = false; // 划掉倍数
}
}
int cnt = 0;
for (int k = 2; k < n; k++) if (isPrime[k]) cnt++;
return cnt;
}
}复杂度
时间复杂度
O(n log log n)
每个合数只被其质因子划掉,划倍数总次数 ≈ n·Σ(1/p) ≈ n log log n,近似线性
空间复杂度
O(n)
一张长度为 n 的布尔表 is_prime,记录每个数是否被划掉 → O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 计数质数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
埃氏筛的时间复杂度怎么来的?+
划倍数总次数 ≈ n·(1/2+1/3+1/5+…) = n·Σ(1/p),由质数倒数和的渐近性,约等于 O(n log log n)。
为什么从 i*i 开始划、外层到 √n 停?+
i*i 之前的倍数已被更小质数划过;大于 √n 的合数其小因子也都处理过了,无需再筛。
想再快还有什么办法?+
用「欧拉筛(线性筛)」让每个合数只被其最小质因子划一次,达到严格 O(n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 计数质数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。