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

洛谷P1217 [USACO1.5]回文质数 Prime Palindromes 题目描述

题目描述

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

写一个程序来找出范围 [a,b] (5 le a < b le 100,000,000)[a,b](5≤a

当然呢我们直接暴力会时间超限

先给出时间超限的代码，当然对于小数据还是可以通过的嘿嘿。

#include
using namespace std;
bool hw(int n)
{
	int t = n;
	int sum = 0;
	while (t)
	{
		sum = sum * 10 + t % 10;
		t /= 10;
	}
	if (sum == n)
		return true;
	else
		return false;
}
bool zs(int n)
{
	for (int i = 2; i < sqrt(n); i++)
	{
		if (n % i == 0)
			return false;
	}
	return true;
}
int main()
{
	int x, y;
	cin >> x >> y;
	for (int i = x; i <= y; i++)
	{
		if (zs(i) && hw(i))
			cout << i << 'n';
	}
	return 0;
}

---

接下来给出完全ac的代码

接下来完成第一个任务判断回文数

bool hw(int n)
{
	int t = n;
	int sum = 0;
	while (t)
	{
		sum = sum * 10 + t % 10;
		t /= 10;
	}
	if (sum == n)
		return true;
	else
		return false;
}

懂得都懂，不多bb；

然后就是判断质数呢，还有怎样防止时间超限呢？？

首先正整数除偶数2以外都不是质数，时间大约减少一半，其次通过百度可以知道位数是偶数位的一定不是回文质数除了11.。。。。。。。

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

bool ws(int k)  //没有偶数位数的回文质数
{
	if (k >= 10 && k < 100 && k != 11 || k >= 1000 && k < 10000)return false;
	if (k >= 100000 && k < 1000000 || k >= 10000000 && k < 100000000)return false;
	return true;
}

这样就能过八个测试点了但是最后一个测试点是真的狗啊一直TEL

int main()
{
	int x, y;
	scanf("%d%d", &x, &y);
	if (x == 2)
		printf("2n");
	if (x % 2 == 0)
		x++;
	y = min(y, 9999999);
	for (int i = x; i <= y; i+=2)
	{
		if (hw(i) && ws(i) && zs(i))
			printf("%dn", i);
	}
	return 0;
}

如果不加min这句判断是不会过最后一个测试点的。。。。。。。

这样的话就万无一失了哈哈哈哈

目录

题目描述

题目描述

---