Problem J27: Prime Filtering / 素数筛选问题

版权信息： · 素数枚举基础题 · 实战训练章节

任务总览

题目描述

给定两个正整数 $m$ 和 $n$（$m < n$），请输出区间 $[m, n]$ 中所有的​ 素数 ​。

输出格式要求：​ 每行打印 5 个素数 ​，用空格隔开。

输入格式

一行两个正整数 $m$ 和 $n$，满足 $1 \leq m < n \leq 10 ^ 5$。

输出格式

输出区间 $[m, n]$ 中所有的素数，每行打印 5 个，用空格分隔。最后一行不足 5 个素数时可少于 5 个。

输入输出样例

输入示例

198 260

输出示例

199 211 223 227 229
233 239 241 251 257

题目分析与解法

这是一个经典的​ 素数区间筛选问题 ​，有以下几种解法：

✅ 方法一：逐个判断（适合 $n \leq 10 ^ 5$）

• 对区间 $[m, n]$ 中的每个数调用 is_prime() 判断是否为素数；
• 时间复杂度：$O((n - m) \cdot \sqrt{ n })$，适用于中小区间。

✅ 方法二：埃拉托色尼筛法（筛出 $n$ 内所有素数）

• 提前构建 is_prime[] 表示每个数是否为素数；
• 适合 $n \leq 10 ^ 6$；
• 时间复杂度：$O(n \log \log n)$，更适合大量素数查询。

时间复杂度分析