LeetCode 补充题 214. 不大于 n 的全部素数
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ 204. 计数质数
:::
给定非负整数
n，按升序返回闭区间[0,n]中的全部素数。
示例 1：
输入：
n = 7
输出：[2,3,5,7]
提示：
0 <= n <= 5000000-
0和1不是素数。
题意分析
逐个试除会反复检查同一因子。筛法反过来枚举素数并标记其倍数，最后剩下的未标记位置就是素数；本题还要包含可能为素数的上界 n。
解法：埃氏筛
核心思路
[!blue]
composite[x]表示 x 已被发现是合数。扫描到尚未标记的 i 时，它就是素数，用它标记后续倍数。从
i*i开始，是因为2*i、3*i、…、(i-1)*i都含有更小的因子，早已由前面的素数标记。只需处理到平方不超过 n 的 i，每个合数就会被至少一个较小因子覆盖。最后从 2 扫描到 n，收集未标记的位置。本题包含上界 n，因此数组长度和循环上界都要覆盖 n，不能沿用“统计小于 n 的素数”的边界。
解题步骤
- n<2 时返回空结果，否则创建长度为 n+1 的合数标记数组。
- 从 2 开始扫描满足 i<=n/i 的数，已标记为合数的跳过。
- 对未标记的 i，从 i×i 开始按步长 i 标记所有不超过 n 的倍数。
- 从 2 到 n 升序收集未标记的数。
代码实现
class Solution {
public List<Integer> listPrimes(int n) {
if (n < 2) {
return new ArrayList<>();
}
boolean[] composite = new boolean[n + 1];
for (int i = 2; i <= n / i; i++) {
if (composite[i]) {
continue;
}
for (int multiple = i * i; multiple <= n; multiple += i) {
composite[multiple] = true;
}
}
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (!composite[i]) {
primes.add(i);
}
}
return primes;
}
}
func listPrimes(n int) []int {
if n < 2 {
return []int{}
}
composite := make([]bool, n+1)
for i := 2; i <= n/i; i++ {
if composite[i] {
continue
}
for multiple := i * i; multiple <= n; multiple += i {
composite[multiple] = true
}
}
primes := []int{}
for i := 2; i <= n; i++ {
if !composite[i] {
primes = append(primes, i)
}
}
return primes
}
复杂度分析
- 时间复杂度：$O(n\log\log n)$。
- 空间复杂度：$O(n)$。
关键点总结
[!green]
埃氏筛标记合数，从每个质数的平方开始标记倍数；扫描包含 n 的整个范围，收集未标记的数。
易错点总结
[!yellow]
- 上界 n 包含在结果范围中，数组和循环都要覆盖该下标。
- 0 和 1 即使没有被标记也不是素数，收集必须从 2 开始。
- 倍数标记从 i×i 开始；外层用 i<=n/i 判断平方边界，避免先计算过大的平方。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 204. 计数质数 | 中等 | 都可使用埃氏筛；该题统计严格小于 n 的素数个数，本题返回不大于 n 的全部素数，边界与输出形式不同。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！