C/C++实现洛谷P1217 [USACO1.5] 回文质数 Prime Palindromes 题目（题解）

黒井深

已于 2024-06-12 16:29:43 修改

阅读量272

点赞数 1

文章标签： c语言 c++ 算法

于 2023-10-28 15:46:48 首次发布

本文链接：https://blog.csdn.net/qq_55149044/article/details/134091567

版权

题目：

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

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

首先可以得知，int类型可能放不下后面这么大的数，那么我选择用 long long int 一步到位

那么按照基本流程，根据提示可以得知，我们需要先判断回文数，再判断质数（素数）

//判断是否为回文数（是返回true，不是返回false）
bool huiwen(long long int n) {
	//存储倒序过来的n
	long long int un = 0;
	//循环用的临时变量
	long long int temp = n;
	while (temp) {//倒序操作
		un = un * 10 + (temp % 10);
		temp /= 10;
	}
	if (n == un) {
		return true;
	}
	else {
		return false;
	}
}
//判断是否为质数（是返回true，不是返回false）
bool zhishu(long long int n) {
	for (long long int i = 2; i <n; i++) {
		if (0 == n % i) {
			return false;
		}
	}
	return true;
}
int main() {
	long long int a,b;
	cin >> a>>b;
	for (long long int i = a; i <= b; i+=2)
	{
		
		if (huiwen(i)) {
			if (zhishu(i)) {
				cout << i << endl;
			}
		}
		
	}
	return 0;
}

好，以上便是这道题的解（）

如果你拿这个去提交答案，那么恭喜你...超时了！

那么下面便是我的优化思路：

一、首当其冲的便是判断素数，这部分的循环判断的范围可以优化成从输入数n到其开方：sqrt(n)

当然还有个质数表的优化方法，好像是叫孪生质数，但是emmm比较难理解，我就没用那种方法

详情请看：【算法】素数（质数）判断方法

//优化后的质数判断（用sqrt需要引用头文件：#include<math.h>）
bool zhishu(long long int n) {
	for (long long int i = 2; i <= sqrt(n); i++) {
		if (0 == n % i) {
			return false;
		}
	}
	return true;
}

二、优化完质数判断，此时再去提交应该就剩最后一个测试点超时了，我看了半天的题解，发现他们也是对数据的测试范围做优化，比如：

1.除去11以外，数字位数是偶数的没有回文质数

2.从a,b的循环可以只循环奇数，因为偶数肯定不是质数，这样还能减少函数调用次数

3.数字个位是0的回文数只有0，但测试范围从5开始，所以可以排除数字个位是0的数字

4.100000000（1亿）肯定不是回文质数

所以以后再有超时的情况，我们就可以直接对输入的数先提前找好各种逻辑关系，排除掉一大批一眼就知道不行的数，这样可以尽量避免超时

那么优化后的完整代码：

#include<iostream>
#include<math.h>

using namespace std;

bool weishu(long long int n) {
	//除去11以外，数字位数是 偶数 的没有回文质数
	//100000000（1亿）肯定不是回文质数
	if ((1000 <= n && n <= 9999) || (100000 <= n && n <= 999999) || (10000000 <= n && n <= 99999999) || (100000000 == n))return false;
	return true;
}

bool huiwen(long long int n) {
	//存储倒序过来的n
	long long int un = 0;
	//循环用的临时变量
	long long int temp = n;
	//先判断个位是不是0.要是0的话直接就返回false，因为数字个位是0的回文数只有0
	if (0 == n % 10) {
		return false;
	}
	while (temp) {//倒序操作
		un = un * 10 + (temp % 10);
		temp /= 10;
	}
	if (n == un) {
		return true;
	}
	else {
		return false;
	}
}

bool zhishu(long long int n) {
	for (long long int i = 2; i <= sqrt(n); i++) {
		if (0 == n % i) {
			return false;
		}
	}
	return true;
}

int main() {
	long long int a,b;
	cin >> a>>b;
	//进行奇数循环，因为偶数肯定不是质数
	if (0 == a % 2) {
		a++;
	}
	for (long long int i = a; i <= b; i+=2)
	{
		if (weishu(i)) {
			if (huiwen(i)) {
				if (zhishu(i)) {
					cout << i << endl;
				}
			}
		}
	}
	return 0;
}