本文主要是介绍P1217 [USACO1.5] 回文质数 Prime Palindromes题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
因为151既是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以151是回文质数。
写一个程序来找出范围[a,b](5≤a<b≤100,000,000)(一亿)间的所有回文质数。
输入输出格式
输入格式
第一行输入两个正整数a和b
输出格式
输出一个回文质数的列表,一行一个
代码
#include<bits/stdc++.h>
using namespace std;
bool book[100000001];
void prime(int b){//埃氏筛选法 memset(book, true, sizeof(book));book[1]=false;int n=sqrt(b);for(int i=2;i<=n;i++){if (book[i]){for(int j=2;j<=b/i;j++)//质数的整数倍一定不是质数 book[i*j]=false;}}
}
bool isHWS(int num){int temp=num,ans=0;while (temp!=0) {ans=ans*10+temp%10;temp/=10;}if (ans==num)return true;elsereturn false;
}
int main(){int a,b;cin>>a>>b;//b<=10000000这个判断条件来自:除了11以外,一个数的位数是偶数的话,不可能为回文素数。//如果一个回文素数的位数是偶数,则它的奇数位上的数字和与偶数位上的数字和必然相等;//根据数的整除性理论,容易判断这样的数肯定能被11整除,所以它就不可能是素数。if (b>=10000000)b=9999999;prime(b);if(a>b)return 0;if (a%2==0) a++;//除了2以外,2的倍数都不是质数 for (int i=a;i<=b;i+=2) {//偶数都不考虑 if (book[i] && isHWS(i))cout<<i<<endl;}return 0;
}
这篇关于P1217 [USACO1.5] 回文质数 Prime Palindromes题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!