【题目来源】
洛谷：P1217 [USACO1.5] 回文质数 Prime Palindromes - 洛谷
【题目描述】
因为 $151 $ 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 \(151\) 是回文质数。
写一个程序来找出范围 \([a,b](5\le a\lt b\le 100,000,000)\)（一亿）间的所有回文质数。
【输入】
第一行输入两个正整数 \(a\) 和 \(b\)。
【输出】
输出一个回文质数的列表，一行一个。
【输入样例】
5 500
【输出样例】
5
7
11
101
131
151
181
191
313
353
373
383
【解题思路】
【算法标签】
《洛谷 P1217 回文质数》 #素数判断,质数,筛法# #USACO#
【代码详解】
#include <bits/stdc++.h> // 包含标准库头文件（万能头文件）
using namespace std; // 使用标准命名空间/*** 判断一个数是否是回文数* @param n 要判断的数字* @return 如果是回文数返回true，否则返回false*/
bool isPalindrome(int n)
{int s = 0, k = n; // s存储反转后的数字，k是n的临时副本while (k != 0) {s *= 10; // 左移一位s += k % 10; // 添加最后一位数字k /= 10; // 移除最后一位数字}if (s == n) // 比较反转后的数字和原数字return true;return false;
}/*** 判断一个数是否是质数* @param n 要判断的数字* @return 如果是质数返回true，否则返回false*/
bool isPrime(int n)
{// 从3开始检查到√n，步长为2（跳过偶数）for (int i = 3; i <= sqrt(n); i = i + 2) {if (n % i == 0) // 如果能被整除，不是质数return false;}return true;
}/*** 主函数 - 程序入口* @return 程序执行状态码（0表示成功）*/
int main()
{int a, b; // 定义变量：查找范围[a,b]cin >> a >> b; // 输入查找范围// 确保从奇数开始查找（偶数不可能是质数）if (a % 2 == 0) a++;// 优化：超过10000000的数字不可能是回文质数if (b > 10000000) b = 10000000;// 遍历范围内的奇数，查找回文质数for (int i = a; i <= b; i = i + 2) {// 如果是回文数且是质数if (isPalindrome(i) && isPrime(i)) {cout << i << endl; // 输出该回文质数}}return 0; // 程序正常结束
}
【运行结果】
5 500
5
7
11
101
131
151
181
191
313
353
373
383