输出区间 [A, B] 内所有"本身是素数且数字对换后也是素数"的两位数。
如果一个两位数本身是素数,且它的数字位置对换后仍是素数,则称为绝对素数,例如 13(13 和 31 都是素数)。
给定两个正整数 A、B(10 < A < B < 100),求出 ≥ A 且 ≤ B 的所有绝对素数,从小到大输出,每行一个。
素数判定数位对换区间枚举试除法
| 项目 | 说明 |
|---|---|
| 输入 | 一行两个正整数 A、B |
| 输出 | 每行一个绝对素数,从小到大 |
| 范围 | 10 < A < B < 100 |
| 处理对象 | 两位数(10 ~ 99) |
| 判定条件 | 本身是素数 且 对换后也是素数 |
10b + a逐个检查 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 | — | 跳过 |
19 本身是素数 ✅
对换后是 91
91 = 7 × 13,不是素数 ❌
所以 19 不满足条件
❌ 不输出 19
11 是素数 ✅
对换后还是 11,也是素数 ✅
"回文式"的两位素数(11)天然满足条件
✅ 输出 11
输出 11、13、17 ✓
如果个位是 0,对换后得到的是一位数(前导 0)。比如 20 → 02 = 2。
| 数字 | 十位 a | 个位 b | 对换后 | 说明 |
|---|---|---|---|---|
| 20 | 2 | 0 | 2 | 个位是 0,对换后变成一位数 |
| 30 | 3 | 0 | 3 | 同上 |
| 13 | 1 | 3 | 31 | 正常两位 |
3、7 两个因子即可判断两位数的素性——这是一个很好的优化思路。对每个数从 2 试到 √n 判素数
用埃氏筛把 99 以内的素数全标出来,之后 O(1) 查询
| 方案 | 本题运算量 | 代码量 |
|---|---|---|
| 试除法 | 几百次 | 约 8 行 |
| 埃氏筛 | 约 100 次 + 查询 | 约 15 行 |
输入两个两位数 A 和 B(空格分隔),程序会逐个检查并列出绝对素数。
点按钮开始 →
#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(那就是原数,没有对换)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
11 20 | 11 / 13 / 17 | 题面样例 |
11 11 | 11 | 单个数字 |
19 19 | (无输出) | 19 是素数,但 91 = 7 × 13 不是 |
10 30 | 11 / 13 / 17 / 31 中的 13、17… | 需按区间逐个判定 |
90 99 | (无输出) | 该区间内没有满足条件的数 |
(n % 10) * 10 + n / 10。只需几个整型变量。
✅ 不到 1000 次运算,瞬间完成。这题考的是素数判定和数位拆分的组合。
// 素数判定的标准写法 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 依次筛 | 所有"同时满足多个条件"的枚举题 |