Problem J23: Reversible Primes / 可逆素数

版权信息： · 枚举与素数筛法基础题

任务总览

题目描述

我们称一个正整数为​** 可逆素数** ​，当且仅当：

• 它本身是一个​素数 ​；
• 将其十进制表示的所有数字** 倒转后形成的新数** 仍然是素数。

例如：

• 107 是素数；
• 将 107 倒过来得到 701；
• 701 也是素数；
• 所以 107 和 701 构成一对可逆素数。

注意：输出时只输出两者中的较小值，且不可重复。

输入格式

输入两个正整数 $m$ 和 $n$，满足：

• $100 < m < n < 1000$

  ---

  输出格式

  输出所有位于区间 $[m, n]$ 内的可逆素数对中较小的那个数，​ 按升序排列 ​，每行输出一个。

  ---

  输入输出样例

  输入示例

  100 200
  

  输出示例

  107
  113
  131
  149
  157
  179
  199
  

  ---

  题目分析与解法

  ✅ 解题步骤：

  1. 枚举 $[m, n]$ 内的所有数；
  2. 判断该数是否为​ 素数 ​；
  3. 将该数反转，构造一个新整数；
  4. 判断该反转后的整数是否也是素数；
  5. 若满足条件，记录原数；
  6. 最终输出​ 所有满足条件的原数（较小值） ​，按升序排列，且避免重复。

  ---

  时间复杂度分析

  | 操作 | 复杂度 | | --------- | ------------------------ - | | 素数判定 | $O(\sqrt{ n })$ | | 区间枚举 | $O(n - m)$ | | 总体复杂度 | 可接受（$< 900$ 范围） |

  ---