【洛谷 P1217】[USACO1.5] 回文质数 Prime Palindromes 题解（欧拉筛法+回文判断）

[USACO1.5] 回文质数 Prime Palindromes

题目描述

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

写一个程序来找出范围 $[a,b](5\le a<b\le 100,000,000)$（一亿）间的所有回文质数。

输入格式

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

输出格式

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

样例 #1

样例输入 #1

5 500
1

样例输出 #1

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

提示

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$ 的回文数：

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;//(处理回文数...)
         }
     }
 }

1
2
3
4
5
6
7
8

---

思路

先用欧拉筛法得到 2 到 b 的质数，存储在数组 pri 中，然后输出大于 a 的回文质数。

---

AC代码

#include 
#define AUTHOR "HEX9CF"
using namespace std;

const int N = 1e8 + 7;

int a, b;
int pri[N];
bool vis[N];
int cnt = 0;

bool check(int x)
{
    int t[10];
    int l = 0;
    while (x > 0)
    {
        t[l++] = x % 10;
        x /= 10;
    }
    for (int i = 0; i < l; i++)
    {
        if (t[i] != t[l - i - 1])
        {
            return 0;
        }
    }
    return 1;
}

void euler(int x)
{
    for(int i = 2; i <= x; i++) {
        if(!vis[i]) {
            pri[cnt++] = i;
        }
        for(int j = 0; j < cnt && i * pri[j] <= x; j++) {
            vis[i * pri[j]] = 1;
            if(!(i % pri[j])) {
                break;
            }
        }
    }
}

int main()
{
    cin >> a >> b;
    euler(b);
    for (int i = 0; i < cnt; i++)
    {
        if (pri[i] >= a && check(pri[i]))
        {
            printf("%d\n", pri[i]);
        }
    }
    return 0;
}

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59