CSP/信奥赛C++语法基础刷题练习（23）：洛谷P1217：[USACO1.5] 回文质数 Pr ...

CSP/信奥赛C++语法基础刷题练习（23）：洛谷P1217：[USACO1.5] 回文质数 Prime Palindromes

题目形貌

因为                                    151                              151                  151 既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以                                    151                              151                  151 是回文质数。
写一个程序来找出范围                                    [                         a                         ,                         b                         ]                         (                         5                         ≤                         a                         <                         b                         ≤                         100                         ,                         000                         ,                         000                         )                              [a,b] (5 \le a < b \le 100,000,000)                  [a,b](5≤a<b≤100,000,000)（一亿）间的全部回文质数。
输入格式

第一行输入两个正整数                                    a                              a                  a 和                                    b                              b                  b。
输特别式

输出一个回文质数的列表，一行一个。
样例 #1

样例输入 #1

1. 5 500

复制代码

样例输出 #1

1. 5
2. 7
3. 11
4. 101
5. 131
6. 151
7. 181
8. 191
9. 313
10. 353
11. 373
12. 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 的回文数：

1. for (d1 = 1; d1 <= 9; d1+=2) {    // 只有奇数才会是素数
2.      for (d2 = 0; d2 <= 9; d2++) {
3.          for (d3 = 0; d3 <= 9; d3++) {
4.            palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)
5.          }
6.      }
7. }

复制代码

  66分代码

1. #include<bits/stdc++.h>
2. using namespace std;
3. /*思路：（70分：部分测试点超时）
4. 函数1：判断一个数是否是质数
5. 函数2：判断一个数是否是回文数
6. */
7. int a,b;
8. //判断一个数是否是质数
9. bool isPrime(int x){
10.         if(x<=1) return false;
11.         for(int i=2;i<=sqrt(x);i++){
12.                 if(x%i==0) return false;
13.         }
14.         return true;
15. }
16. //判断一个数是否是回文数
17. bool isHw(int x){
18.         int tmp=x;//记录x的值用于过程运算
19.         int y=0;
20.         while(tmp){
21.                 y=y*10+tmp%10;
22.                 tmp/=10;
23.         }
24.         if(x==y) return true;
25.         else return false;
26. }
27. int main(){
28.         cin>>a>>b;
29.         for(int i=a;i<=b;i++){
30.                 if(isPrime(i) && isHw(i)){
31.                         cout<<i<<endl;
32.                 }
33.         }
34.         return 0;
35. }

复制代码

  88分代码

1. #include<bits/stdc++.h>
2. using namespace std;
3. /*思路：（88分：部分测试点超时）
4. 函数1：判断一个数是否是质数
5. 函数2：判断一个数是否是回文数
6. ---优化思路：先判断是否是回文，再判断是否是质数----
7. ---因为质数判断的函数时间复杂度较高，而回文判断的函数时间复杂度较低----
8. */
9. int a,b;
10. //判断一个数是否是质数
11. bool isPrime(int x){
12.         if(x<=1) return false;
13.         for(int i=2;i<=sqrt(x);i++){
14.                 if(x%i==0) return false;
15.         }
16.         return true;
17. }
18. //判断一个数是否是回文数
19. bool isHw(int x){
20.         int tmp=x;//记录x的值用于过程运算
21.         int y=0;
22.         while(tmp){
23.                 y=y*10+tmp%10;
24.                 tmp/=10;
25.         }
26.         if(x==y) return true;
27.         else return false;
28. }
29. int main(){
30.         cin>>a>>b;
31.         for(int i=a;i<=b;i++){
32.                 if(isHw(i) && isPrime(i)){//优化的关键修改在这儿
33.                         cout<<i<<endl;
34.                 }
35.         }
36.         return 0;
37. }

复制代码

  100分代码

1. #include<bits/stdc++.h>
2. using namespace std;
3. /*思路：（100分）        
4. ---新增优化：减少b的值---
5.     >b在10^7到10^8之间时，位数是偶数位，不可能为回文数素数
6.     >除了11以外，一个数的位数是偶数的话，不可能为回文数素数。
7.     >如果一个回文素数的位数是偶数，则它的奇数位上的数字和与偶数位上的数字和必然相等；
8.     >根据数的整除性理论，容易判断这样的数肯定能被11整除，所以它就不可能是素数。
9. */
10. int a,b;
11. //判断一个数是否是质数
12. bool isPrime(int x){
13.         if(x<=1) return false;
14.         for(int i=2;i<=sqrt(x);i++){
15.                 if(x%i==0) return false;
16.         }
17.         return true;
18. }
19. //判断一个数是否是回文数
20. bool isHw(int x){
21.         int tmp=x;//记录x的值用于过程运算
22.         int y=0;
23.         while(tmp){
24.                 y=y*10+tmp%10;
25.                 tmp/=10;
26.         }
27.         if(x==y) return true;
28.         else return false;
29. }
30. int main(){
31.         cin>>a>>b;
32.         b=min(b,9999999); //优化b的最大值
33.         for(int i=a;i<=b;i++){
34.                 if(isHw(i) && isPrime(i)){//优化的关键修改在这儿
35.                         cout<<i<<endl;
36.                 }
37.         }
38.         return 0;
39. }

复制代码

  文末彩蛋：
  点击王老师青少年编程主页有更多精彩内容
[code][/code]
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。