2025年洛谷P1217题解（全AC）

科技前沿 • 2025-02-22 13:09 • 阅读 52

大家好，我是讯享网，很高兴认识大家。

一、题目描述

因为 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 是回文质数。

写一个程序来找出范围 [a,b](5≤a<b≤100,000,000)（一亿）间的所有回文质数。

二、思路展开

首先，我们知道要筛选回文数和质数，由于回文数只需判断数字是否左右对称，而质数需要遍历寻找因子，显然找到回文数更加容易。

所以我们先筛选出范围内的回文数，再筛选出其中的质数。

在打代码前，有几点性质需要了解。

2.1 回文数

2.1.1 回文数的性质

可以被11整除
不存在偶数位的回文数
一位数都是回文数

2.1.2 如何检索回文数

在处理回文数之前，学习高精度的写法是必须的。

int p = x; //x为需要存储的数 int pL = 0; //有几位数 while(p>0){ number[pL++] = p%10; //一位一位赋值 p/=10; }

讯享网

比如我们给x赋值352,那么存到number数组里的效果就是:

讯享网number[0] >>2 number[1] >>5 number[2] >>3

没错，反向存入~~

讯享网

接下来对两边的数字进行检查就好啦：

//pL为数位长度 if(pL%2==0){ for(;i<=pL/2-1;i++){ //偶数位 if(number[i]!=number[pL-1-i]){ return 0; } } return 1; } for(;i<=(pL-1)/2-1;i++){ //奇数位 if(number[i]!=number[pL-1-i]){ return 0; } } return 1;

2.2 质数

2.2.1 质数的性质

不能被1和自身以外的数整除
2是质数

2.2.2 如何检索质数

由于根号x * 根号x = x，所以可以知道所有因子关于x对称。

举个例子，10 = 2 * 5 = 5 * 2 = sqrt(10)*sqrt(10)。所以前乘数只需要扫到sqrt(x)就可以停了。

这样能节省一半的算法~

由于题目将范围设定在[5,100 000 000]之间，所以我们先过滤掉两位以外的偶数位数(四位数、六位数、八位数)。

原因是这类数可以被11整除，不是质数。因此我们在前期就直接筛去它们。

最后对着每个数直接判断三次就行啦

三、完整代码

讯享网#include <bits/stdc++.h> using namespace std; int min_(int a,int b){ if(a<b) return a; else return b; } bool checkLen(int x){//检查位数和奇偶 if((x>=1000&&x<=9999)||(x>=&&x<=)){ return 0; } return 1; } bool checkMalin(int x){ //检查回文 int number[10]; int p = x; int pL = 0; while(p>0){ number[pL++] = p%10; p/=10; } int i=0; if(pL%2==0){ for(;i<=pL/2-1;i++){ //偶数位 if(number[i]!=number[pL-1-i]){ return 0; } } return 1; } for(;i<=(pL-1)/2-1;i++){ if(number[i]!=number[pL-1-i]){ return 0; } } return 1; } bool checkPrime(int x){ //检查质数 if(x==2){ return 1; } for(int i=2;i<=sqrt(x);i++){ if(x%i==0){ return 0; } } return 1; } int main(){ int min,max; scanf("%d %d",&min,&max); if(min%2==0){ min++; //奇数开始 } max = min_(,max); //回文质数 for(int i=min;i<=max;i+=2){ //奇数 if(!checkLen(i)){ continue; } if(!checkMalin(i)){ continue; } if(!checkPrime(i)){ continue; } printf("%d\n",i); } return 0; }

感谢来访与阅读，欢迎各路大佬批评与指点意见