回文质数 C++题解

回文质数

内存限制： 64 MiB 时间限制： 1000 ms 标准输入输出 题目类型： 传统 评测方式： 文本比较

题目描述

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

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

输入格式

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

输出格式

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

样例

样例输入

复制5 500 

样例输出

复制5
7
11
101
131
151
181
191
313
353
373
383

#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 5;
int l, r;
int a[8];
bitset<N> vis;
vector<int> prime, huiwen;
void Prime(int n) {
	for(int i = 2; i <= n; i++) {
		if(!vis[i]) prime.push_back(i);
		for(auto j : prime) {
			if(i * j > n) break;
			vis[i * j] = 1;
			if(i % j == 0) break;
		} 
	} 
} 
void Huiwen() {
	for(auto i : prime) {
		int x = 0, t = i, cnt = 0;
		while(t >= 10) a[++x] = t % 10, t /= 10;
		a[++x] = t;
		for(int i = 1; i <= x / 2; i++) {
			if(a[i] == a[x - i + 1]) cnt++; 
		} 
		if(cnt == x / 2) huiwen.push_back(i);
	} 
} 
int main() {
	vis[0] = vis[1] = 1;
	scanf("%d %d", &l, &r);
	Prime(r), Huiwen();
	for(auto i : huiwen) {
		if(i < l) continue;
		printf("%d\n", i);
	} 
	return 0;
} 
//我的方法是先判断质数再判断回文，当然也可以先判断回文再判断质数