GESP 题解库 / 4 级题解 / [GESP样题 四级] 绝对素数 · 第 23 / 25 题
GESP样题 四级 · B3939 · 简单

绝对素数

输出区间 [A, B] 内所有"本身是素数且数字对换后也是素数"的两位数。

📊
10 < A < B < 100
区间范围
🔢
两位数
处理对象
⚡
O(区间长度 × √n)
时间复杂度
🎯
素数判定 + 数位对换
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

如果一个两位数本身是素数,且它的数字位置对换后仍是素数,则称为绝对素数,例如 13(13 和 31 都是素数)。

给定两个正整数 A、B(10 < A < B < 100),求出 ≥ A 且 ≤ B 的所有绝对素数,从小到大输出,每行一个。

💡
人话翻译:只处理两位数。对区间内每个数,检查两件事:① 它自己是素数;② 十位和个位对换后的数也是素数。两个条件都满足就输出。

🔍 关键词提取

素数判定数位对换区间枚举试除法

已知条件

项目说明
输入一行两个正整数 A、B
输出每行一个绝对素数,从小到大
范围10 < A < B < 100
处理对象两位数(10 ~ 99)
判定条件本身是素数 且 对换后也是素数

需要解决的问题

02
思维导图
整理解题思路的全貌
🔍 双重素数判定
📥 读入
A、B(10 < A < B < 100)
只需处理两位数
从 A 枚举到 B
从小到大输出
✅ 第一关
检查 n 是否为素数
试除 2 ~ √n
不是素数直接跳过
两位数只需试到 9
🔄 数位对换
a = n / 10(十位)
b = n % 10(个位)
swap = b × 10 + a
例如 13 → 31
✅ 第二关
检查 swap 是否为素数
也是素数 → 输出
否则跳过
两个条件缺一不可
03
样例手算推导
样例 [11, 20] 逐个检查

🧮 样例:A = 11,B = 20

逐个检查 11 到 20。

数字本身是素数?对换后对换后是素数?结论
11✅ 是11✅ 是输出 11
12❌ 偶数21—跳过
13✅ 是31✅ 是输出 13
14❌ 偶数41—跳过
15❌ 5 的倍数51—跳过
16❌ 偶数61—跳过
17✅ 是71✅ 是输出 17
18❌ 偶数81—跳过
19✅ 是91❌ 91 = 7 × 13不输出
20❌ 偶数02 = 2—跳过
1
19 为什么不是绝对素数?

19 本身是素数 ✅

对换后是 91

91 = 7 × 13,不是素数 ❌

所以 19 不满足条件

❌ 不输出 19

2
为什么 11 可以?

11 是素数 ✅

对换后还是 11,也是素数 ✅

"回文式"的两位素数(11)天然满足条件

✅ 输出 11

输出 11、13、17 ✓

🧮 一个易错点:对换后可能不是两位数

如果个位是 0,对换后得到的是一位数(前导 0)。比如 20 → 02 = 2。

数字十位 a个位 b对换后说明
20202个位是 0,对换后变成一位数
30303同上
131331正常两位
🔑
本题不需要特判这种情况——因为个位是 0 的两位数(10、20、…、90)全部都是偶数或含因子 5,本身就不是素数,第一关就被筛掉了。但如果你想写得更严谨,可以加一句判断。
另外注意:个位是偶数或 5 的两位数都不是素数(除了它自己等于 2 或 5,但那是位数为 1 的情况),所以实际只需试除 3、7 两个因子即可判断两位数的素性——这是一个很好的优化思路。
04
解法对比
试除法 vs 预处理素数表

⚔️ 解法对比

🟢 试除法(推荐) 推荐

对每个数从 2 试到 √n 判素数

  • 单个判定 O(√n)
  • 两位数只需试到 9
  • 代码 8 行
  • 区间最多 90 个数
💡
为什么够用:区间长度不到 90,每个数最多试除 3、7 等几个因子,总运算量不到几百次。

🟠 先筛出 1 ~ 99 的素数表

用埃氏筛把 99 以内的素数全标出来,之后 O(1) 查询

  • 预处理 O(99 log log 99)
  • 查询 O(1)
  • 代码稍长
  • 对本题是过度设计
⚠️
什么时候值得:如果区间很大(比如要判 10⁶ 以内的数),筛法优势明显。本题只有两位数,试除法更简单直接。

📈 性能对比

方案本题运算量代码量
试除法几百次约 8 行
埃氏筛约 100 次 + 查询约 15 行
05
算法流程图
枚举区间并双重判定
开始读入 A、Bn 从 A 枚举到 Bn 是素数吗?是 ✓继续否 ✗跳过对换数位:swap = (n % 10) × 10 + (n / 10)swap 是素数吗?是 ✓输出 n否 ✗跳过区间内还有数吗?结束n 加 1
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🔍 绝对素数查找器

输入两个两位数 A 和 B(空格分隔),程序会逐个检查并列出绝对素数。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

// 判断 x 是否为素数
bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

int main() {
    int A, B;
    scanf("%d %d", &A, &B);

    for (int n = A; n <= B; n++) {
        if (!isPrime(n)) continue;              // 第一关:本身必须是素数

        // 数位对换:n = 10a + b -> 10b + a
        int a = n / 10;                          // 十位
        int b = n % 10;                          // 个位
        int sw = b * 10 + a;

        if (isPrime(sw)) printf("%d\n", n);      // 第二关:对换后也是素数
    }
    return 0;
}
🔑
为什么 isPrime 里循环条件写 i * i <= x?因为如果 x 有因子,必然存在一个因子 ≤ √x——所以只需试除到 √x 就够了。比试除到 x 快得多,而且 i * i <= x 比 i <= sqrt(x) 避免了浮点误差。

📖 关键几行怎么看

代码作用为什么这样写
if (x < 2) return false;特殊值0 和 1 都不是素数,必须单独处理
i * i <= x试除上界只需到 √x,且用整数比较避免浮点误差
a = n / 10; b = n % 10;取十位与个位整数除法截断,正好取十位
sw = b * 10 + a;对换把个位当十位、十位当个位
⚠️
三个坑:① isPrime 没处理 x < 2 (虽然本题 n ≥ 11,但函数应写完整);② 试除时写成 i < x,效率低且没必要;③ 对换公式写成 a * 10 + b(那就是原数,没有对换)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
11 2011 / 13 / 17题面样例
11 1111单个数字
19 19(无输出)19 是素数,但 91 = 7 × 13 不是
10 3011 / 13 / 17 / 31 中的 13、17…需按区间逐个判定
90 99(无输出)该区间内没有满足条件的数
✅
自查清单:① 两个条件都判了吗?② 对换公式对吗?③ isPrime 完整吗?

🚨 易错点清单

⚠️
只判一个条件:必须两个条件都满足——本身是素数且对换后也是素数。例如 19 本身是素数但 91 不是。
⚠️
对换公式写错:应该是 (n % 10) * 10 + n / 10。
⚠️
isPrime 漏掉 < 2 的处理:写完整更稳妥。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O((B−A) × √n)
空间复杂度
O(1)
区间长度
≤ 90
试除次数
每个数 ≤ 9 次

时间怎么算的?

空间都用在哪?

只需几个整型变量。

✅ 不到 1000 次运算,瞬间完成。这题考的是素数判定和数位拆分的组合。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 素数判定的标准写法
bool isPrime(int x) {
    if (x < 2) return false;
    if (x == 2) return true;
    if (x % 2 == 0) return false;        // 偶数快速筛掉
    for (int i = 3; i * i <= x; i += 2)  // 只试奇数因子
        if (x % i == 0) return false;
    return true;
}

// 两位数的数位拆分与合并
int tens = n / 10;          // 十位
int ones = n % 10;          // 个位
int swapped = ones * 10 + tens;

// 更通用的"反转数字"
int rev = 0, t = n;
while (t > 0) { rev = rev * 10 + t % 10; t /= 10; }

// 埃氏筛(区间很大时使用)
vector<bool> isP(100, true);
isP[0] = isP[1] = false;
for (int i = 2; i * i < 100; i++)
    if (isP[i]) for (int j = i * i; j < 100; j += i) isP[j] = false;

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
素数判定试除到 √n所有素数相关题目
数位拆分/ 10 和 % 10数位统计、回文数、数字反转
双重条件枚举两个 if 依次筛所有"同时满足多个条件"的枚举题
🌟
思考题:如果把范围扩展到所有整数(不限两位数),"绝对素数"还有哪些?(提示:三位数以上就不存在了——因为数字重排后如果能得到偶数或 5 的倍数,就不是素数。例如任何包含偶数位的三位数,把偶数放到末位就得到偶数(大于 2)→ 不是素数。所以"绝对素数"(任意重排都是素数)最多只到两位数,这是个很漂亮的结论。)