一、题目简介题目链接洛谷 P1217 [USACO1.5] 回文质数题目题意给定两个整数 a,b5 ≤ a b ≤ 100000000按从小到大的顺序输出区间 [a,b] 内所有既是回文数又是质数的数字。核心难点数据范围最大可达 1 亿普通暴力枚举极易超时必须结合数学性质优化才能稳定 AC。二、必备数学核心知识点解题关键这道题的所有优化思路都基于两个重要数学规律看懂直接减半计算量除 11 外所有偶数位的回文数一定不是质数比如 2 位、4 位、6 位、8 位回文数都能被 11 整除必然是合数。因此我们只需要枚举 1、3、5、7 位回文数直接跳过所有偶数位回文数。大于 2 的质数一定是奇数回文数首位等于末位因此首位只能是奇数1、3、5、7、9无需遍历偶数开头的数字。三、解法一暴力枚举法新手入门、易懂但超时1. 解题思路遍历区间 [a,b] 的每一个数字先判断是否为回文数再判断是否为质数双重条件满足即输出。逻辑最简单完全贴合题意适合新手理解基础概念。2. 完整代码#include stdio.h // 判断质数 int zhishu(int x) { if(x 2) return 0; // 只遍历到平方根优化质数判断 for(int i 2; i * i x; i) { if(x % i 0) return 0; } return 1; } // 判断回文数 int huiwen(int x) { int tmp x; int rev 0; // 反转数字 while(tmp 0) { rev rev * 10 tmp % 10; tmp / 10; } // 反转后与原数相等即为回文数 return rev x; } int main() { int a, b; scanf(%d%d, a, b); for(int i a; i b; i) { if(huiwen(i) zhishu(i)) { printf(%d\n, i); } } return 0; }3. 优缺点分析✅ 优点逻辑直白、代码简洁、零基础能看懂完美适配初学练习。❌ 缺点遍历所有数字存在大量无效计算数据量大千万级、亿级时必然超时无法通过洛谷全部测试点。四、解法二逐位构造回文法稳妥AC、官方推荐思路1. 解题思路利用数学结论直接手动构造合法回文数不再盲目遍历所有数字。仅构造 1、3、5、7 位奇数位回文数单独处理唯一的 2 位回文质数 11构造完成后仅判断是否为质数、是否在区间内。计算量大幅缩减稳定 AC。2. 完整代码#include stdio.h int zhishu(int x) { if(x 2) return 0; for(int i 2; i * i x; i) { if(x % i 0) return 0; } return 1; } int main() { int a,b; scanf(%d%d,a,b); int pal; // 1位回文质数5、7 for(int d1 5; d1 7; d1 2) { pal d1; if(pal a pal b zhishu(pal)) printf(%d\n,pal); } // 唯一2位回文质数11 pal 11; if(pal a pal b zhishu(pal)) printf(%d\n,pal); // 3位回文d1 d2 d1 for(int d11;d19;d12) for(int d20;d29;d2) { pal d1*100 d2*10 d1; if(pal b) continue; if(pal a zhishu(pal)) printf(%d\n,pal); } // 5位回文d1 d2 d3 d2 d1 for(int d11;d19;d12) for(int d20;d29;d2) for(int d30;d39;d3) { pal d1*10000 d2*1000 d3*100 d2*10 d1; if(pal b) continue; if(pal a zhishu(pal)) printf(%d\n,pal); } //7位回文d1 d2 d3 d4 d3 d2 d1 for(int d11;d19;d12) for(int d20;d29;d2) for(int d30;d39;d3) for(int d40;d49;d4) { pal d1*1000000 d2*100000 d3*10000 d4*1000 d3*100 d2*10 d1; if(pal b) continue; if(pal a zhishu(pal)) printf(%d\n,pal); } return 0; }3. 优缺点分析✅ 优点严格遵循题目优化思路无冗余计算通过率 100%适合竞赛刷题。❌ 缺点代码行数较多多层循环嵌套写法稍繁琐。五、解法三前半段翻转构造法最优极简AC、你的原版代码1. 解题思路这是本题最优、最简洁的竞赛写法。核心技巧枚举回文数的前半段翻转拼接生成完整奇数位回文数。举例前半段 12 → 翻转后半段 1 → 拼接得到回文 121前半段 13 → 拼接得到 131。无需多层嵌套用一个函数统一生成所有 3/5/7 位回文数代码极度精简效率拉满。2. 完整代码逐行解析#include stdio.h // 质数判断函数 int zhishu(int x) { if(x2){ return 0; } for(int i2;i*ix;i){ if(x%i0){ return 0; } } return 1; } // 核心前半段翻转生成回文数 int Prime(int y) { int result y; y / 10; // 去掉最后一位保留前半段用于翻转 while(y0){ result result*10 y%10; // 逐位拼接翻转后的数字 y / 10; } return result; } int main() { int a,b; scanf(%d %d,a,b); // 单独处理1位数回文质数 for(int ia;ibi10;i){ if(zhishu(i)){ printf(%d\n,i); } } // 单独处理唯一2位回文质数11 if(a1111b){ printf(11\n); } // 批量生成3、5、7位回文数 for(int i10;i100000;i){ int p Prime(i); if(pb) break; // 剪枝超出上限直接退出循环 if(pazhishu(p)){ printf(%d\n,p); } } return 0; }3. 核心函数深度解析回文生成函数 Prime(y)先用 result 存储前半段数字砍掉前半段最后一位避免重复拼接循环取出剩余数字的个位拼接到末尾实现翻转效果最终生成标准奇数位回文数。剪枝优化生成的回文数一旦超过上限 b直接 break后续数字只会更大无需遍历极大节省时间。4. 优缺点分析✅ 优点代码精简、逻辑高级、计算量最小、速度最快是竞赛首选写法。❌ 缺点需要理解翻转拼接的核心逻辑新手需要稍加琢磨。六、三种解法全方位对比解法核心思路效率是否AC适用场景暴力枚举法遍历所有数双重判断极低大数据超时新手入门理解题意逐位构造法分层构造合法回文数高完全AC课堂练习、稳妥刷题前半段翻转法翻转拼接生成回文最高完全AC竞赛、追求精简高效七、刷题总结P1217 是经典的暴力优化数学思维入门题核心考点不是代码熟练度而是用数学性质减少无效计算。新手学习建议先看懂暴力写法理解题意再掌握翻转构造最优解既能吃透基础又能学会算法优化思维完美适配 CSP-J、入门编程竞赛的基础题型。