[USACO1.5] 回文质数 Prime Palindromes
利用偶数位回文除 11 外都不是质数的性质，只构造少量奇数位回文再试除判素。
OJ: luogu
题目 ID: P1217
难度:普及/提高-
标签:数论枚举构造python
日期: 2026-06-18 22:15
题意
给出区间 [a,b]，输出其中所有既是回文数、又是质数的整数，每个数单独一行。
思路
如果从 a 到 b 逐个扫描，再分别判断回文和质数，区间最大可以到 10^8，Python 和 C++ 都会做很多无用检查。
更好的方向是：不要在区间中寻找回文数，而是直接构造回文数。
一个关键性质是：
- 除了
11以外，所有偶数位回文数都能被11整除，因此不可能是质数。
所以需要检查的候选只剩：
- 一位数回文；
- 特判
11； - 奇数位回文。
奇数位回文可以由一个“前半部分种子”构造出来：
| 种子 | 构造结果 |
|---|---|
12 |
121 |
305 |
30503 |
9999 |
9999999 |
对种子字符串 s，构造式是：
text
s + s[-2::-1]也就是保留最后一位作为中心，再把中心左边的部分反向接到右侧。
最后按从小到大的种子枚举回文数，落在 [a,b] 中时再用试除法判断质数即可。
Python 知识
/home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：用map(int, input().split())读取一行两个整数。/home/rainboy/mycode/hugo-blog/content/program_language/python/math_tools.md：用math.isqrt做精确整数平方根，质数试除时不依赖浮点数。text[-2::-1]是切片写法：从倒数第二个字符开始，向左反向取到开头。- 把答案先存成字符串列表，最后
"\n".join(answer)输出，适合这种多行结果。
代码
python
from math import isqrt
def is_prime(x):
if x < 2:
return False
if x == 2:
return True
if x % 2 == 0:
return False
for d in range(3, isqrt(x) + 1, 2):
if x % d == 0:
return False
return True
def make_odd_palindrome(seed):
text = str(seed)
return int(text + text[-2::-1])
a, b = map(int, input().split())
answer = []
for x in range(1, 10):
if a <= x <= b and is_prime(x):
answer.append(str(x))
if a <= 11 <= b:
answer.append("11")
for seed in range(10, 10000):
value = make_odd_palindrome(seed)
if value > b:
break
if value >= a and is_prime(value):
answer.append(str(value))
print("\n".join(answer))Guide 风格代码
cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：
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-08-14 15:18
* update_at: 2026-08-14 15:18
*/
/* P1217 回文质数：组合「回文判断」和「质数判断」两个函数，只枚举少量回文候选。 */
#include <iostream>
// 试除法判断 x 是否为质数
bool is_prime(int x) {
if (x < 2) {
return false;
}
if (x == 2) {
return true;
}
if (x % 2 == 0) {
return false; // 除 2 以外的偶数都不是质数
}
for (int d = 3; 1LL * d * d <= x; d += 2) {
if (x % d == 0) {
return false;
}
}
return true;
}
// 判断 x 正着读和倒着读是否相同
bool is_palindrome(int x) {
int reversed = 0;
int rest = x;
while (rest > 0) {
reversed = reversed * 10 + rest % 10; // 把 rest 的最低位搬到 reversed 前面
rest /= 10;
}
return reversed == x;
}
// 由种子 x 构造奇数位回文数：12 -> 121，305 -> 30503
int make_odd_palindrome(int x) {
int result = x;
x /= 10; // 最低位作为回文的中心，不再参与镜像
while (x > 0) {
result = result * 10 + x % 10;
x /= 10;
}
return result;
}
int main() {
int a, b;
std::cin >> a >> b;
// 一位数回文
for (int x = 1; x <= 9; x += 1) {
if (a <= x && x <= b && is_prime(x)) {
std::cout << x << '\n';
}
}
// 唯一可能是质数的偶数位回文数是 11
if (a <= 11 && 11 <= b && is_prime(11)) {
std::cout << 11 << '\n';
}
// 由种子 10..9999 构造 3、5、7、9 位回文数，按升序出现
for (int seed = 10; seed <= 9999; seed += 1) {
int palindrome = make_odd_palindrome(seed);
if (palindrome > b) {
break; // 种子越大构造结果越大，后面的都不在区间内
}
if (palindrome < a) {
continue;
}
// 构造保证是回文，这里组合两个判断函数作为校验
if (is_palindrome(palindrome) && is_prime(palindrome)) {
std::cout << palindrome << '\n';
}
}
return 0;
}Pythonic 写法
回文 + 质数：
python
import math
def is_prime(x):
return x>1 and all(x%d for d in range(2,int(math.isqrt(x))+1))
def is_pal(x):
s=str(x); return s==s[::-1]
a,b=map(int,input().split())
# odd digits only except 11 for large ranges optimization optional
for x in range(a,b+1):
if is_pal(x) and is_prime(x):
print(x)复杂度
最多枚举 10 到 9999 的种子，构造出的奇数位回文覆盖到 10^8 以内。每个候选数用试除法判断质数，单次复杂度是 c 是输出答案个数。
总结
这题的关键不是把判素数写得很快，而是先把候选数量降下来。看出偶数位回文数的整除性质后，只构造奇数位回文，就能避免扫描整个大区间。
