P1217 [USACO1.5] 回文质数 Prime Palindromes

题目描述

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

写一个程序来找出范围 （一亿）间的所有回文质数。

输入格式

第一行输入两个正整数 和 。

输出格式

输出一个回文质数的列表，一行一个。

输入输出样例 #1

输入 #1

1
5 500

输出 #1

1
2
3
4
5
6
7
8
9
10
11
12
5
7
11
101
131
151
181
191
313
353
373
383

思考

首次

我看到题目第一时间狂喜，这不就是素数判断+回文判断水题吗，于是我直接速写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<stdio.h>
#include<math.h>
#define N 20
int isprime(int m)
{
    if(m<=1)return 0;
    else{
        for(int i=2;i<=sqrt(m);i++){
            if(m%i==0)return 0;
        }
    }
    return 1;
}
int hui(int m)
{
    int num[N],j=0;
    while(m!=0){
        num[j]=m%10;
        m/=10;
        j++;
    }
    if(j==1)return 1;
    else{
        for(int i=0,k=j-1;i<k;i++,k--){
        if(num[i]!=num[k])return 0;
        }
        return 1;
    }
}

int main(void){
    int m,n;
    scanf("%d %d",&m,&n);
    for(int i=m;i<=n;i++){
        if(isprime(i)&&hui(i))
        printf("%d\n",i);
    }
}

交题结果 image.png

有点蒙毕竟以我蒟蒻码量有点难处理 从哪里着手减少复杂度呢

第二次

  • 素数判断可以更简便，2之后只查奇数节约一半时间
  • 显而易见的，回文数比素数少得多，因此可以先判断回文数再判断素数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<stdio.h>
#include<math.h>
#define N 20
int isprime(int m)
{
    if(m<=1)return 0;
    else{
        for(int i=2;i<=sqrt(m);i++){
            if(m%i==0)return 0;
        }
    }
    return 1;
}
int hui(int m)
{
    int num[N],j=0;
    while(m!=0){
        num[j]=m%10;
        m/=10;
        j++;
    }
    if(j==1)return 1;
    else{
        for(int i=0,k=j-1;i<k;i++,k--){
        if(num[i]!=num[k])return 0;
        }
        return 1;
    }
}

int main(void){
    int m,n;
    scanf("%d %d",&m,&n);
    for(int i=m;i<=n;i++){
        if(hui(i)&&isprime(i))
        printf("%d\n",i);
    }
}

提交结果

image.png

还是超时 但是意料之中，我的回文判断还只停留在回文字符串水平，开数组判断确实离谱

第三次

只有回文判断优化一条路可走了

数字反转法：通过数学运算反转数字，然后和原数比较。

1
2
3
4
5
6
7
8
9
10
11
12
  int hui(int m)
  {
      int original = m, reversed = 0;
      
       while(m > 0) {
	      reversed = reversed * 10 + m % 10;
	      //    ↑累加数字    ↑取最后一位
	      m /= 10;          // 去掉最后一位
	  }

      return original == reversed;
  }

优雅多了

优势：

  - 不需要数组，节省空间

  - 时间复杂度 O(d)，d是数字位数

  - 代码简洁

image.png

出来了：）

到最后才看到题底下的hintQAQ

提示 2: 要产生正确的回文数，你可能需要几个像下面这样的循环。

产生长度为 的回文数：

1
2
3
4
5
6
7
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;//(处理回文数...)
         }
     }
 }