枚举区间内的整数,使用 $O(\sqrt{x})$ 的试除法判断素数并输出,注意无素数时需输出 0 字节。
OJ: roj
题目 ID: 5032
难度:入门
标签:模拟数学素数判定
创建: 2026-10-08 22:49
更新: 2026-10-08 22:49
形式化题目
给定两个正整数
正解
思路
题目要求找出
判断一个整数
- 若
,则 既不是素数也不是合数(例如 不是素数),直接返回 false。 - 若
,我们尝试用从 开始的正整数 去除 。如果遇到 ,说明 有非平凡的约数,是一个合数。 - 关键在于优化:合数的约数总是成对出现的。如果
,其中 ,那么必然有 ,也就是 。因此,我们在试除时,只需要枚举到 即可。在代码中通常写为 i * i <= x,以避免浮点开方的精度误差。
在主函数中,枚举 is_prime(x) 为真,就输出
代码
python
#!/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:41
# update_at: 2026-10-08 22:41
import sys
def is_prime(x: int) -> bool:
"""判断 x 是否为素数:1 既不是素数也不是合数,只需试除到 sqrt(x)。"""
if x < 2:
return False
i = 2
while i * i <= x:
if x % i == 0:
return False
i += 1
return True
def solve() -> None:
"""读入 a、b,按题意逐行输出 [a, b] 区间内的所有素数。"""
data = iter(map(int, sys.stdin.buffer.read().split()))
a, b = next(data), next(data)
# 每个素数占一行(含最后一行);区间内没有素数时必须输出 0 字节,
# 所以只能用 write 拼串,不能用 print('\n'.join(...))(那会多出一个换行)。
sys.stdout.write("".join(f"{x}\n" for x in range(a, b + 1) if is_prime(x)))
if __name__ == "__main__":
solve()cpp
/**
* 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:41
* update_at: 2026-10-08 22:41
*/
#include <iostream>
using namespace std;
typedef long long ll;
// 判断 x 是否为素数:1 既不是素数也不是合数,x < 2 直接排除;
// 只需试除到 sqrt(x),用 i * i <= x 作上界可避免浮点开方的精度问题。
bool is_prime(ll x) {
if (x < 2) return false;
for (ll i = 2; i * i <= x; i++) {
if (x % i == 0) return false;
}
return true;
}
// 逐行输出 [a, b] 内的素数;区间内一个素数都没有时自然不输出任何字节。
void solve() {
ll a, b;
if (!(cin >> a >> b)) return;
for (ll i = a; i <= b; i++) {
if (is_prime(i)) {
cout << i << "\n";
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}复杂度
- 时间复杂度:判断单个数
是否为素数需要 时间。对于区间 ,最坏情况下需要判断所有数,时间复杂度为 。在 时,最坏情况(如 )的理论上界约为 186 万次。经过实测,实际约 30 万次内层迭代,远小于时限,最坏点运行时间极短(C++ 约 9 ms,Python 约 30 ms)。 - 空间复杂度:由于只是枚举并输出,未使用额外的大型数组或数据结构,空间复杂度为
。
总结
- 算法:枚举
,用试除法判素数;时间复杂度 。 - ★★ 空输出是 0 字节而非空行(本题最易错):当区间内没有素数时,输出必须是 0 字节 而非空行。例如
1 1与20000 20000测试点都是 0 字节。- V1 反事实:如果在逻辑外无条件输出换行
\n(使得无素数点变为空行输出),会导致测试点 10/10 全部失败。
- V1 反事实:如果在逻辑外无条件输出换行
- ★ 四种输出写法对照表(以 Python 为例):
| 写法 | 结果 | 分析 |
|---|---|---|
per-prime write(每个素数各自写) |
10/10 ✅ | 安全、符合标准的输出习惯。 |
write(join + '\n')(仅非空时) |
10/10 ✅ | 拼好串再输出,仅在串非空时带 \n。 |
print(join) |
8/10 ❌ | Python print 自带末尾换行。无素数时 print('') 会输出一个 \n(1 字节),导致空输出点错。 |
join 无尾换行 |
2/10 ❌ | 所有素数挤在一行或违背了最后一行自带行尾换行的标准规范。 |
- 1 不是素数;当
且为合数时也无数可输;全部 20000 个 单点已验证,其中 17738 个无素数点全部输出 0 字节,正确处理边界非常关键。 - ★ 验证强度摘要:本题解使用了异源 Eratosthenes 筛交叉验证;针对 17 组大区间/边界进行严格测试验证;最坏点性能表现优异(C++ 9.3 ms / Python 30.6 ms);V2 字面量不含硬编码素数表,试除起点
2是唯一内嵌常数。 - 复杂度:本题运算量实际很小,实际约 30 万次内层迭代,最坏上界约 186 万次,不构成性能瓶颈。