[算法] 回文质数

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

因为题目太长以后都默认放在后面了，可以通过右边的目录快速定位

思路

构建回文数-> 判断是否为质数

思路是先构造回文数，然后判断这个数的否为质数

题目给的范围很大，所有如果使用暴力的方法肯定是超时，因为对那个筛质数不是很熟，所以想用 先构造回文数 ，再 判断是否为质数 的方式来节省一定的时间，毕竟所有的偶数除去，少了一大半，然后又是回文数，所以剩下的数并不是很多。

build(int l, int r, int cnt, int len)方法用于生成回文数

其中的 l 为最高位的下标，r 为最低位下标，cnt 用于统计当前已经构造了多少位，每一位构造的时候只需要使用这一位的下标然后进行枚举 j 在指定范围内 pow(10, index) * j 加到 sum 即可，这样从两头向中间，对应的两个位置枚举相同的数即可。

特判

  1. 长度为 1 的时候，从 5 开始，int j = (len == 1 ? 5 : (r == 0 ? 1 : 0));
  2. 不能越界 lboard <= sum <= rboard,if (sum + temp > rboard) break; 和 if (sum >= lboard && cnt == 0 && isPrime(sum))
  3. len 为奇数的时候,最后 l 和 r 会正好相等，只加其中一个
1
2
3
4
5
if (l == r) {
    temp = (int)pow(10, r) * j;
} else {
    temp = (int)pow(10, l) * j + (int)pow(10, r) * j;
}

Coding

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
#include <iostream>
#include <math.h>

using namespace std;

int lboard, rboard;

// 判断是否为质数
bool isPrime(int n) {
    for (int i = 2; i <= (int)sqrt(n); i++)
        if (n % i == 0)
            return false;
    return true;
}

// 构建回文数
void build(int l, int r, int sum, int cnt, int len) {
    if (l < r || cnt <= 0) {
        if (sum >= lboard && cnt == 0 && isPrime(sum))
            cout << sum << endl; 
        return;
    }
    for (int j = (len == 1 ? 5 : (r == 0 ? 1 : 0)); j <= 9; j += (r == 0 ? 2 : 1)) {
        int temp = 0;
        if (l == r) {
            temp = (int)pow(10, r) * j;
        } else {
            temp = (int)pow(10, l) * j + (int)pow(10, r) * j;
        }
        if (sum + temp > rboard)
            break;
        build(l -1, r + 1, sum + temp, cnt - (l == r ? 1 : 2), len);
    }
}

// 求给定数的长度
int len(int n) {
    int ret = 0;
    while (n > 0) {
        ret++;
        n /= 10;
    }
    return ret;
}

int main() {
    
    cin >> lboard >> rboard;
    int llen = len(lboard), rlen = len(rboard);

    for (int i = llen - 1; i < rlen; i++) {
        build(i, 0, 0, i + 1, i + 1);
    }
    return 0;
}

题目描述

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

写一个程序来找出范围 [a,b](5 <= a < b <= 100,000,000) ( 一亿)间的所有回文质数;

输入输出格式

输入格式：

第 1 行: 二个整数 a 和 b .

输出格式：

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

输入输出样例

输入样例#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

说明

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

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