type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定整数
n ,返回 所有小于非负整数 n 的质数的数量 。示例 1:
示例 2:
示例 3:
解法一:试除更小的质数
合数一定有至少一个质因子。
与其拿
i 去除所有更小的整数,不如只除更小的质数;并且只需要除到
√i 为止(i 若有因子,必有一个 ≤ √i)。从 2 开始,一个个试:判断
i 是否能被“之前已经找到的质数”整除;若都不能整除,i 就是新质数。复杂度
- 时间:平均远好于朴素
O(n√n),但严格上界仍可到O(n√n);
- 空间:
O(π(n))(存质数列表,π(n)是质数个数)。
解法二:埃氏筛
“合数 = 有质因子 × 另一个整数”。只要遇到一个质数,就能一次性批量剔除它的倍数,比对每个数逐一试除要高效得多。
维护一个布尔数组
is_prime[0..n],初始都当作“可能是质数”。遇到质数 i,就把它的所有倍数标记为合数。关键优化:
- 只筛到
i*i <= n:超过√n的质数,其最小未标记倍数至少是i*i,但i*i > n时无需再筛。
- 从
i*i开始标记:2*i, 3*i, ..., (i-1)*i早就被更小的素因子标记过了,避免重复工作。
复杂度
- 时间:
O(n log log n)(经典结论,极接近线性)。
- 空间:
O(n)。
解法三:线性筛(欧拉筛)
埃氏筛会“重复标记”某些合数(被多个质因子轮番扫到)。
线性筛通过“按质数列表驱动 + 遇到能整除就 break”,确保每个合数仅被它的最小质因子标记一次,从而把总操作数控制在线性级别。
复杂度
- 时间:
O(n)
- 空间:
O(n)
解法四:分段筛(Segmented Sieve)
埃氏筛的内存瓶颈是
O(n) 的布尔数组。当
n 很大、内存有限,无法开 O(n) 数组时(例如区间质数统计、离线大数据处理),可以用分段筛把范围切成多个“可放入内存的小块”,每块用同一批小质数进行局部筛除,内存开销变为
O(B + √n)。具体步骤:
- 先把 [2, √n] 的质数用普通埃氏筛求出来;
- 然后按块(如每块长度
B)处理区间[L, R],用这些小质数去标记当前块里的合数;
- 块内剩下没被标记的就是该段内的质数。
复杂度
- 时间:与埃氏筛同阶,
O(n log log n);
- 空间:
O(√n + B),其中B是块大小(可调)。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-204-质数计数
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 200] 岛屿数量
下一篇
[Leetcode 206] 反转链表
