c++版本回文质数 Prime Palindromes 题解（洛谷）

给大家分享一句我很喜欢我话： 知不足而奋进，望远山而前行！！！ 铁铁们，成功的路上必然是孤独且艰难的，但是我们不可以放弃，远山就在前方，但我们能力仍然不足，所有我们更要奋进前行！！！ 今天我们更新了c++回文质数内容， 🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝互三互三！！！！！

什么是回文质数？

其实通俗的来说就是一个既是回文数，又是指数的数 回文质数是指从左到右和从右到左读都相同的质数。换句话说，这是一种同时具备回文性质和质数属性的数字。例如，121、131、313都是回文质数，因为它们不仅是质数（只能被1和自身整除），而且从左到右和从右到左读都是一样的。 在寻找回文质数时，需要同时检查一个数字是否是质数和是否是回文数。这涉及到分别检查数字是否能被其他整数整除（质数检查）和数字的各个数字是否对称（回文数检查）。

首先我们看一下题

这就是这个题的大致内容，下面我们来求解一下这道题

带你用c++实现这个题

顾名思义，先回文再质数。搜狗百科解释如下：回文素数是一个既是素数又是回文数的整数。回文素数与记数系统的进位制有关。回文素数是指，对一个整数n(n>11)从左 向右和从右向左读其结果值相同且是素数，即称n为回文素数。除了11，偶数位的数不存在回文质数。（以前不知道那现在知道了）。4位，6位，8位…… 不存在回文质数。因为四位及四位以上的偶数位的回文数都可以被11整除，故不存在偶数位的回文质数。最初几个回文素数:11，101 ，131，151，181，191，313，353，373 383，727，757，787，797，919，929…… 两位回文素数1个，三位回文素数15 个，五位回文素数93个，七位回文素数668 个，九位回文素数5172个。

启发 本题要找出5至1亿内的回文质数，两位的只有11，三位， 五位，七位，才有回文质数，九位的话，1亿显然不是。所以可以缩小些范围，直接检查位数，减少用时。

下面，我们将会建立三个函数，用于检查一个数是否是回文质数，当然，为了节省时间，我们检查的顺序也是有一定规律的

我们将会先检查或者数的位数，因为一个数如果是回质数，那么这个数肯定是奇数位（除了11），

因此，如果一个数是四位数或者六位数，我们将忽略它，我们建一个函数check1用于检查：

bool check1(int n)
{
	if ((1000 <= n && n <= 9999) || ( 100000<=n && n <= 999999))return 0;
	return 1;
	//如果属于这些范围，即使是回文数，也不可能是质数
}

如果符合的话，然后我们将进行下一步，下一步我们将写一个代码用于检查一个数是否是回文数，我们先将其转化为一个字符串，然后将字符串的前面的与后面的一一对应，就可以求出这个数是否符合：

bool check2(int n)
{
	int arr[20];
	int i = 0;
	while (n > 0)
	{
		arr[i] = n % 10;
		n /= 10;
		i++;
	}
	for (int j = 0; j < i / 2; j++)
	{
		if (arr[j] != arr[i - j - 1])return 0;	
	}
	return 1;
}

如果符合这一个，我们将继续向下进行，下面我么将检查一个数是否是质数，质数（prime number）是指除了1和自身以外，不能被其他正整数整除的大于1的整数。换句话说，质数只有两个正因数：1和它自身。例如，2、3、5、7、11等都是质数。如果一个数大于1并且不是质数，则它被称为合数。

然后我们写下以下代码用于检查：

bool check3(int n)
{
	if (n == 2)return 1;
	for (int i = 2; i <= sqrt(n); i++)
	{
		if (n % i == 0)return 0;
	}
	return 1;
}

这样我们便能得到规定区域内的所有回文质数了！

全部代码

#include<iostream>

using namespace std;
int l, r;
bool check1(int n)
{
	if ((1000 <= n && n <= 9999) || ( 100000<=n && n <= 999999))return 0;
	return 1;
	//如果属于这些范围，即使是回文数，也不可能是质数
}

bool check2(int n)
{
	int arr[20];
	int i = 0;
	while (n > 0)
	{
		arr[i] = n % 10;
		n /= 10;
		i++;
	}
	for (int j = 0; j < i / 2; j++)
	{
		if (arr[j] != arr[i - j - 1])return 0;	
	}
	return 1;
}


bool check3(int n)
{
	if (n == 2)return 1;
	for (int i = 2; i <= sqrt(n); i++)
	{
		if (n % i == 0)return 0;
	}
	return 1;
}


int main()
{
	
	scanf("%d%d", &l, &r);
	if (l == 2)printf("2\n");
	if (l % 2 == 0)l += 1;
	r = min(9999999, r);
	for (int i = l; i <= r; i+=2)
	{
		if (check1(i) == 0)continue;
		if (check2(i) == 0)continue;
		if (check3(i) == 0)continue;
		printf("%d\n", i);
	}

	return 0;
}

这里主函数中的2我们要特殊对待，因为2是回文质数，但它不能作为l，因为为了节省时间，我们要将l设为奇数才可以，如果是2，就输出然后+1，如果是其他偶数，就+1，因为其他偶数不可能是回文质数。

再有一个点就是你会发现我在代码中使用的是scanf和printf，没用cin和cout，因为前者的运行速度要比后者快一些，为了防止超时，所以我们用的scanf和printf