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

题目描述

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

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

输入格式

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

输出格式

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

解法1-暴力打表

见 https://blog.sevin.cn/posts/12620/

解法2-正常带有技巧的打表

首先分析回文质数的前提

  • 回文数
  • 质数

然后就想到

  • 质数的条件：除了2以外的2的倍数都不是质数
  • 位数是2的倍数的数除了11都不是回文质数，因为这类回文数都能被11整除
  • 判断速度：位数>回文数>质数

通过上述内容，我们就能写出速度较快的打表。

代码实现

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
#include <iostream>
#include <cmath>
using namespace std;

bool digit_count_check(long long num) {
	if (num == 11) return true; // 11是特例要先处理 
	int digit_count = (int)log10(num);
	if (digit_count % 2 != 0) return false;
	else return true;
}

bool is_pal(long long num) {
	long long origin = num;
	long long reserved = 0;
	while (num != 0) {
		int temp = num % 10;
		reserved = reserved * 10 + temp;
		num /= 10;
	}
	return origin == reserved;
}

bool is_prime(long long num) {
	bool status = true;
	for (int i=2; i * i <= num; i++) {
		if (num % i == 0) {
			status = false;
			break;
		}
	}
	if (num == 1) status = false;
	return status;
}

int main() {
	long long a,b,num;
	cin >> a >> b;
	for (int i=a/2*2+1; i <= b; i += 2) {
		if (!digit_count_check(i)) continue;
		if (!is_pal(i)) continue;
		if (is_prime(i)) cout << i << endl;
	}
	
	return 0;
}

解法三-生成回文数

这道题我们可以先生成回文数然后进行质数判断。在生成中因为上文提到的除了11，位数不能是二的倍数，所以我们只需要生成位数是奇数的就行。

生成回文数的方法案例

产生长度为 55 的回文数：

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

这一部分是题干有给的信息

代码实现

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
60
61
62
63
64
65
66
#include <iostream>
using namespace std;

long long n[100000];

bool is_prime(long long num) {
	bool status = true;
	for (int i=2; i * i <= num; i++) {
		if (num % i == 0) {
			status = false;
			break;
		}
	}
	if (num == 1) status = false;
	return status;
}

int main() {
	long long a,b,x=3;
	cin >> a >> b;
	n[0]=5;n[1]=7;n[2]=11;//2位数和1位数只有这三个是回文质数
	for (int d1=1; d1 <= 9; d1++) {
		for (int d2=0; d2 <= 9; d2++) {
			n[x] = d1 * 100 + d2 * 10 + d1;
			x++;
		}
	} // 3位数
	for (int d1=1; d1 <= 9; d1++) {
		for (int d2=0; d2 <= 9; d2++) {
			for (int d3=0; d3 <= 9; d3++) {
				n[x] = d1 * 10000 + d2 * 1000 + d3 * 100 + d2 * 10 + d1;
				x++;
			}
		}
	} // 5位数
	for (int d1=1; d1 <= 9; d1++) {
		for (int d2=0; d2 <= 9; d2++) {
			for (int d3=0; d3 <= 9; d3++) {
				for (int d4=0; d4 <= 9; d4++) {
					n[x] = d1 * 1000000 + d2 * 100000 + d3 * 10000 + d4 * 1000 + d3 * 100 + d2 * 10 + d1;
					x++;
				}
			}
		}
	} //7位数
	for (int d1=1; d1 <= 9; d1++) {
		for (int d2=0; d2 <= 9; d2++) {
			for (int d3=0; d3 <= 9; d3++) {
				for (int d4=0; d4 <= 9; d4++) {
					for (int d5=0; d5 <= 9; d5++) {
						n[x] = d1 * 100000000 + d2 * 10000000 + d3 * 1000000 + d4 * 100000 + d5 * 10000 + d4 * 1000 + d3 * 100 + d2 * 10 + d1;
						x++;
					}
				}
			}
		}
	} //9位数
	for (int i=0; i < x; i++) {
		if (n[i] < a) continue;
		else if (n[i] > b) break;
		bool status = is_prime(n[i]);
		if (status) cout << n[i] << endl;
	}
	
	return 0;
}