2465: 【普及-】【P1217】回文质数 Prime Palindromes
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：16
解决：6
题目描述
因为 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 是回文质数。
写一个程序来找出范围 （一亿）间的所有回文质数。
输入
第一行输入两个正整数 和 。
输出
输出一个回文质数的列表，一行一个。
样例输入 复制
5 500样例输出 复制
5
7
11
101
131
151
181
191
313
353
373
383提示
提示：所有偶数位数的回文数（除了11以外）都是11的倍数，因此不是质数。
方法一：直接每个数判断是否回文和是否质数，减少循环范围。
#include<bits/stdc++.h>
using namespace std;
bool isPalindrome(int n) {
int s=0,k=n;
while(k!=0) {
s*=10;
s+=k%10;
k/=10;
}
if(s==n) return true;
return false;
}
bool isPrime(int x) {
if (x==1||x==0) return false;
for (int i=2;i<=sqrt(x);i++) {
if(x%i==0) return false;
}
return true;
}
int main(){
int a,b;
cin>>a>>b;
if(a%2==0) a++;
if(b>=10000000) b=10000000;
for(int i=a;i<=b;i=i+2) {
if(isPalindrome(i)&&isPrime(i)) {
cout<<i<<endl;
}
}
return 0;
}
方法二：使用质数筛。
#include<bits/stdc++.h>
using namespace std;
bool isPrime[100000005];
void aiPrime(int x) {
isPrime[0]=isPrime[1]=0;
for (int i=2;i*i<=x;i++) {
if (isPrime[i]){
for (int j=2;i*j<=x;j++) isPrime[i*j]=0;
}
}
}
bool isHW(int x) {
int a,_x,t;
t=x;
_x=0;
while (t>0) {
a=t%10;
t/=10;
_x=_x*10+a;
}
return x==_x;
}
int main(){
int a,b;
cin>>a>>b;
memset(isPrime,1,sizeof(isPrime));
if (b>=10000000) b=10000000;
/**
通过测试，100000000以内最大的回文质数是9989899
为了减少计算，可以限定aiPrime的最大值为10000000
**/
aiPrime(b);
for (int i=a;i<=b;i++) {
if (isPrime[i]&&isHW(i)) cout<<i<<endl;
}
return 0;
}