使用埃拉托斯特尼筛法求出 n 以内的所有质数,避免使用低效的试除法。
OJ: roj
题目 ID: 5042
难度:入门
标签:质数筛法埃氏筛数学
创建: 2026-10-08 23:34
更新: 2026-10-08 23:34
形式化题目
给定一个整数
正解
思路
本题在题面中明确要求了**「用筛法求出全部质数」**。在编程中,求质数表最容易想到的是对每个数字
埃氏筛的核心思想是:任意质数的倍数一定不是质数。
我们可以用一个布尔数组 is_prime,初始时假设所有数字都是质数。
从最小的质数
关于两个优化点的数学论证:
- 外层循环上界
: 任何合数 必然包含一个不超过 的质因数 。因此, 在前面 的轮次中一定已经被标记为合数。当外层 (即 )时,不会再有新的合数遗漏,无需继续向外层筛。 - 内层循环起点
: 为什么标记 的倍数时可以从 开始?若存在 的倍数 且 ,因为 包含更小的因数 ,必定含有质因数 ( 是 的某质因数)。那么在更早枚举质数 的轮次中, 早就已经被打上标记了。因此从 开始标记不仅正确,且不会遗漏。
代码
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 22:56
# update_at: 2026-10-08 22:56
import sys
from math import isqrt
MAXN = 1000000 # 数组余量(题面上限仅 1000,与 C++ 侧保持一致)
def sieve(n: int) -> list[int]:
"""筛法(埃拉托色尼筛):返回 2..n 内的全部质数,由小到大。"""
is_prime = [True] * (n + 1)
is_prime[:2] = [False, False] # 0 和 1 不是质数
# 外层只需枚举到 sqrt(n):合数必有不超过 sqrt(n) 的质因数
for p in range(2, isqrt(n) + 1):
if not is_prime[p]:
continue # 已被更小的质数筛掉
# 从 p*p 起标记:p 的较小倍数都含更小的质因数,早已被筛过
for j in range(p * p, n + 1, p):
is_prime[j] = False
return [i for i in range(2, n + 1) if is_prime[i]]
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data, 0) # 无输入时取 0,直接走下面的保护分支
if n < 2 or n > MAXN:
return # 题面保证 2 <= n <= 1000,与 C++ 侧保持同一保护
sys.stdout.write(''.join(f"{p}\n" for p in sieve(n)))
if __name__ == "__main__":
solve()/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-08 22:56
* update_at: 2026-10-08 22:56
*/
// main.cpp:用筛法(埃拉托色尼筛)求出 n 以内的全部质数,由小到大每行一个。
#include <iostream>
typedef long long ll;
const int MAXN = 1000000; // 数组余量(题面上限仅 1000,留足空间防数据越界)
bool is_prime[MAXN + 5]; // is_prime[i]:筛完后 i 是否仍为质数
void solve() {
ll n;
if (!(std::cin >> n)) return; // 无输入时安静退出
if (n < 2 || n > MAXN) return; // 题面保证 2 <= n <= 1000
for (ll i = 0; i <= n; ++i) is_prime[i] = true;
is_prime[0] = false; // 0 和 1 不是质数
is_prime[1] = false;
// 外层只需枚举到 sqrt(n):n 以内的合数必有不超过 sqrt(n) 的质因数,
// 它的全部倍数在该质因数处已经被标记过。
for (ll i = 2; i * i <= n; ++i) {
if (!is_prime[i]) continue; // 已被更小的质数筛掉
// 从 i*i 起标记:i 的倍数 i*2 .. i*(i-1) 都含更小的质因数,早已被筛掉。
for (ll j = i * i; j <= n; j += i) is_prime[j] = false;
}
for (ll i = 2; i <= n; ++i) {
if (is_prime[i]) std::cout << i << '\n';
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
solve();
return 0;
}复杂度
- 时间复杂度: 外层遍历
到 的素数,内层去划去倍数。时间复杂度被证明为 。这比试除法 的复杂度要优秀得多。 - 空间复杂度:
。我们需要一个大小为 的布尔数组来标记每个数是否为合数。
总结
1. 算法特征与结构验证
本题要求严格使用筛法,不可偷换为试除法(例如用 % 取模判断 is_prime(x))。
代码中体现出的明确结构证据有:
- 布尔数组标记: C++ 中使用了
bool is_prime[MAXN+5],Python 中使用了is_prime = [True]*(n+1)。 - 倍数标记循环: C++ 中
for (ll j = i*i; j <= n; j += i) is_prime[j] = false;,Python 中for j in range(p*p, n+1, p): is_prime[j] = False。 - 排除了试除: 代码中搜索取模符号
%或者独立的试除判素函数均为空。
值得注意的是,这也是一个平台验证闸门存在盲区的例子:如果将 main.cpp 强行改为逐个数字试除的版本,提交到后台的自动化测试中,仍会报 PASS=10/10 绿灯,系统自身无法识别出非指定算法。因此,对于指定算法题型,必须依靠严格的代码结构和逻辑审查。
2. 扰动实验与临界点刻画(V5 验证)
我们对算法实现的各个部分进行了移除和微调,在
| 扰动方式 | 分歧数 | 结论 |
|---|---|---|
外层 i*i<=n → i<=n/2 |
0 | 冗余但正确(额外增加的轮次只会重复将合数标 false,不影响结果) |
内层起点 i*i → i*2 |
0 | 两者等价( |
外层 → i<=n |
0 | 冗余但正确 |
去掉 is_prime[0]=is_prime[1]=false |
0 | 结果不受影响,因为 |
| 删掉内层倍数标记循环 | 997 | 完全承重(例如 2 3 4 5 6 7 8 9 10) |
删掉 if (!is_prime[i]) continue |
0 | 该句仅提供常数优化,非正确性必需 |
外层 i*i<=n → i*i<n |
11 | ★★ 承重,且临界点可精确刻画(见下文) |
★ 外层边界的精确刻画:
当把循环条件从 i*i <= n 错写成 i*i < n 时,发生分歧的情况恰好发生在 <= 还是 <,并非凭直觉的选择,它决定了当上界本身是一个完全平方数(合数)时,是否能被正确划去。
3. 边界、细节与验证强度摘要
- 边界输出与素数分布: 当
时仅输出 2(占 2 个字节);当时输出 2和3。各个数据点输出行数恰好等于该数值内的素数个数(例如对应 168 个,与独立试除法算出的 完全吻合)。 - 完全异源的 999 穷举验证: 利用不同源的(试除法)生成器,对
的 999 个数字生成期望,C++ 与 Python 分歧数均为 0。且代码中剥离了非必要字面量,无硬编码素数。 - 大数字下的一致性: 两语言版本对数组的大小开了
的余量,保证了如果 ,两者输出依然能够实现完全一致的 78498 行输出,逐字节比对(538468 字节)无任何差异。 - 输出格式: 本题要求从较小质数到大每数一行。对于
,输出 2\n3\n5\n7\n(无多余行尾空格),长度共计为 8 字节。