CSP/信奥赛C++语法基础刷题练习（23）：洛谷P1217：[USACO1.5] 回文质数 Pr
CSP/信奥赛C++语法基础刷题练习（23）：洛谷P1217： 回文质数 Prime Palindromeshttps://i-blog.csdnimg.cn/direct/2b32bb7526e048f481e6120b24e6d58b.png#pic_center
题目形貌
因为 151 151 151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以 151 151 151 是回文质数。
写一个程序来找出范围 [ a , b ] ( 5 ≤ a < b ≤ 100 , 000 , 000 ) (5 \le a < b \le 100,000,000) (5≤a<b≤100,000,000)（一亿）间的全部回文质数。
输入格式
第一行输入两个正整数 a a a 和 b b b。
输特别式
输出一个回文质数的列表，一行一个。
样例 #1
样例输入 #1
5 500
样例输出 #1
5
7
11
101
131
151
181
191
313
353
373
383
提示
Hint 1: Generate the palindromes and see if they are prime.
提示 1: 找出全部的回文数再判断它们是不是质数（素数）.
Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.
提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。
题目翻译来自NOCOW。
USACO Training Section 1.5
产生长度为 5 5 5 的回文数：
for (d1 = 1; d1 <= 9; d1+=2) { // 只有奇数才会是素数
for (d2 = 0; d2 <= 9; d2++) {
for (d3 = 0; d3 <= 9; d3++) {
palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
}
}
}
66分代码
#include<bits/stdc++.h>
using namespace std;
/*思路：（70分：部分测试点超时）
函数1：判断一个数是否是质数
函数2：判断一个数是否是回文数
*/
int a,b;
//判断一个数是否是质数
bool isPrime(int x){
if(x<=1) return false;
for(int i=2;i<=sqrt(x);i++){
if(x%i==0) return false;
}
return true;
}
//判断一个数是否是回文数
bool isHw(int x){
int tmp=x;//记录x的值用于过程运算
int y=0;
while(tmp){
y=y*10+tmp%10;
tmp/=10;
}
if(x==y) return true;
else return false;
}
int main(){
cin>>a>>b;
for(int i=a;i<=b;i++){
if(isPrime(i) && isHw(i)){
cout<<i<<endl;
}
}
return 0;
}
88分代码
#include<bits/stdc++.h>
using namespace std;
/*思路：（88分：部分测试点超时）
函数1：判断一个数是否是质数
函数2：判断一个数是否是回文数
---优化思路：先判断是否是回文，再判断是否是质数----
---因为质数判断的函数时间复杂度较高，而回文判断的函数时间复杂度较低----
*/
int a,b;
//判断一个数是否是质数
bool isPrime(int x){
if(x<=1) return false;
for(int i=2;i<=sqrt(x);i++){
if(x%i==0) return false;
}
return true;
}
//判断一个数是否是回文数
bool isHw(int x){
int tmp=x;//记录x的值用于过程运算
int y=0;
while(tmp){
y=y*10+tmp%10;
tmp/=10;
}
if(x==y) return true;
else return false;
}
int main(){
cin>>a>>b;
for(int i=a;i<=b;i++){
if(isHw(i) && isPrime(i)){//优化的关键修改在这儿
cout<<i<<endl;
}
}
return 0;
}
100分代码
#include<bits/stdc++.h>
using namespace std;
/*思路：（100分）
---新增优化：减少b的值---
>b在10^7到10^8之间时，位数是偶数位，不可能为回文数素数
>除了11以外，一个数的位数是偶数的话，不可能为回文数素数。
>如果一个回文素数的位数是偶数，则它的奇数位上的数字和与偶数位上的数字和必然相等；
>根据数的整除性理论，容易判断这样的数肯定能被11整除，所以它就不可能是素数。
*/
int a,b;
//判断一个数是否是质数
bool isPrime(int x){
if(x<=1) return false;
for(int i=2;i<=sqrt(x);i++){
if(x%i==0) return false;
}
return true;
}
//判断一个数是否是回文数
bool isHw(int x){
int tmp=x;//记录x的值用于过程运算
int y=0;
while(tmp){
y=y*10+tmp%10;
tmp/=10;
}
if(x==y) return true;
else return false;
}
int main(){
cin>>a>>b;
b=min(b,9999999); //优化b的最大值
for(int i=a;i<=b;i++){
if(isHw(i) && isPrime(i)){//优化的关键修改在这儿
cout<<i<<endl;
}
}
return 0;
}
文末彩蛋：
点击王老师青少年编程主页有更多精彩内容
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]