USACO Prime Palindromes (pprime) | 宁心勉学，慎思笃行

这个程序是哈尔滨工业大学的一道作业题，有一位朋友昨晚让我看了这道题目，我发现这道题目还真不是那么简单。学校对刚刚学完数组的大一同学出此题目是否欠妥呢？

现在先看看题目。

Prime Palindromes

The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range.

INPUT FORMAT

Line 1: Two integers, a and b

SAMPLE INPUT (file pprime.in) 5 500

OUTPUT FORMAT

The list of palindromic primes in numerical order, one per line.

SAMPLE OUTPUT (file pprime.out) 5 7 11 101 131 151 181 191 313 353 373 383

这道题目表面上来看比较简单，因为是很基础的算法——求素数和回文数。我先写了一个用循环求余法求素数和检验是否回文的函数，循环查找符合条件的数。

结果不出所料，显然超时。我需要对它进行优化。

所谓优化，无非是三点思路：减少判断是否素数的时间；减少判断是否回文的时间；减少被选数的数量，提高数的精确性。

判断回文并没有什么好优化的地方。就是把前后对称的每位对比一下，防止重复对比即可。

那么判断素数呢？

首先，我们考虑是否可以用筛法求素数。筛法求素数是先把所有的数保存在一起，然后去掉不符合要求的数。每次他找到一个素数，就把这个素数的所有倍数均删除，最后留下的就是需要的素数。

但是这种算法在本题是行不通的，因为数据范围高达 1,000,000,000，如果我们使用筛法，占用内存太大，然而这道题目要求的内存不超过 32MB。

所以我们继续优化求余法。首先，所有的偶数都可以排除（除2以外）；其次，所有偶数位的数都可以排除。因为这样的数的奇数位和偶数位之和可以被11整除，这样的数一定可以被11整除，因此不可能是素数；另外，开头是0、2、4、5、6、8的可以排除，因为这样的回文数一定不是素数。

最后，还可以使用筛法的思路优化素数算法。因为要检查所有的数，对于大数的运算量过大；考虑下面的想法：如果一个数不能整除比他小的所有的素数，那么他一定是素数。原因是一个合数总能被分解为好多素数的积；如果每个质数都不能整除，那么也肯定不会有合数可以整除。

基于上述思路，再结合在求余法中广为应用的优化：只需要判断sqrt(该数)之前是否可以被整除，我们就可以确定，对于小于等于1,000,000,000 的数，只需要保存 10000 之前的素数，然后使用这些质数就可以校验所有的数是否是素数。

那么如何减少数的范围呢？根据偶数位的数一定不成立、开头结尾不能是0、2、4、5、6、8的要求，可以不穷举所有数，直接使用循环生成回文数表。而且，只需要循环数的一半，就可以生成对应的回文数表。

所以最后，我用的算法是这样的：先直接算出10000内的质数表，生成所有小于取值范围并且剪枝过的回文数表，并用质数表去验证是否为质数。

程序如下（最长用时 0.02 秒）

/*
ID:ceeji
PROG:pprime
LANG:C++
*/
 
/*
 * Prime Palindromes
 * By Ceeji
 * Type: Normal
 * For: Friend(Liuhaodong)
 * Date: 2010-10-30
 * Under CC 3.0
 */
 
#include <iostream>
#include <cmath>
#include <string>
#include <fstream>
#include <cstring>
 
 
using namespace std;
 
const int maxl = 10, maxp = 10000;
const char *inf_name = "pprime.in";
const char *ouf_name = "pprime.out";
 
int primes[maxp];
bool isp[maxp];
int plen;
 
bool prime(int i)
{
	if (i == 1)
		return false;
	if (i == 2 || i == 3)
		return true;
	if (i % 2 == 0)
		return false;
	int m = (int)sqrt((float)i);
	if (m > i - 1)
		m = i - 1;
	for (int j = 3; j < m + 1; j += 2)
	{
		if (i % j == 0)
			return false;
	}
	return true;
}
 
 
bool prime2(int i)
{
	if (i < 10001)
	{
		return isp[i];
	}
	if (i == 2 || i == 3)
		return true;
	if (i % 2 == 0)
		return false;
	int m = (int)sqrt((float)i);
	for (int j = 0; j < plen; ++j)
	{
		if(primes[j] > m + 1)
			break;
		if (i % primes[j] == 0)
			return false;
	}
	return true;
}
 
bool palindrome(int i)
{
	char ch[10];
	sprintf(ch, "%d", i);
	int l = strlen(ch);
	for (int p = 0; p < l / 2 + 1; ++p)
	{
		if (ch[p] != ch[l - p - 1])
			return false;
	}
	return true;
}
 
int main(void)
{
	ifstream fin(inf_name);
	ofstream fou(ouf_name);
	int a, b;
	fin >> a >> b;
	/* Find primes which are not bigger than 10000; this will accelerate the prime2 function to check number from 0 to 1,000,000,000. */
	for (int i = 1; i <= 10000; ++i)
	{
		if (prime(i))
		{
			primes[plen++] = i;
			isp[i] = true;
		}
		else
			isp[i] = false;
	}
	for (int i = a; i < 100; ++i)
	{
		if (i >= a && i <= b && palindrome(i) && prime2(i))
		{
			fou << i << endl;
		}
	}
	int now = 0;
	/* Now check for the palindrome with width of 3 */
	for (int i = 1; i < 10; i += 2)
		for (int j = 0; j < 10; ++j)
		{
			if (i == 5)
				continue;
			now = i * 100 + j * 10 + i;
			if (now < a)
				continue;
			if (now > b)
			{
				fou << flush;
				return 0;
			}
			if (prime2(now))
				fou << now << endl;
		}
	/* Now check for the palindrome with width of 5 */
	for (int i = 1; i < 10; i += 2)
	{
		if (i == 5)
			continue;
		for (int j = 0; j < 10; ++j)
			for (int k = 0; k < 10; ++k)
			{
				now = i * 10000 + j * 1000 + k * 100 + j * 10 + i;
				if (now < a)
					continue;
				if (now > b)
				{
					fou << flush;
					return 0;
				}
				if (prime2(now))
					fou << now << endl;
			}
	}
	/* Now check for the palindrome with width of 7 */
	for (int i = 1; i < 10; i += 2)
	{
		if (i == 5)
			continue;
		for (int j = 0; j < 10; ++j)
			for (int k = 0; k < 10; ++k)
				for (int l = 0; l < 10; ++l)
				{
					now = i * 1000000 + j * 100000 + k * 10000 + l * 1000 + k * 100 + j * 10 + i;
					if (now < a)
						continue;
					if (now > b)
					{
						fou << flush;
						return 0;
					}
					if (prime2(now))
						fou << now << endl;
			}
	}
	/* Now check for the palindrome with width of 9 */
	for (int i = 1; i < 10; i += 2)
	{
		if (i == 5)
			continue;
		for (int j = 0; j < 10; ++j)
			for (int k = 0; k < 10; ++k)
				for (int l = 0; l < 10; ++l)
					for (int m = 0; m < 10; ++m)
					{
						now = i * 100000000 + j * 10000000 + k * 1000000 + l * 100000 + m * 10000 + l * 1000 + k * 100 + j * 10 + i;
						if (now < a)
							continue;
						if (now > b)
						{
							fou << flush;
							return 0;
						}
						if (prime2(now))
							fou << now << endl;
			}
	}
	fou << flush;
	return 0;
}

题外话：我帮你整理了包括 AI 写作、绘画、视频（自媒体制作）零门槛 AI 课程 + 国内可直接顺畅使用的软件。想让自己快速用上 AI 工具来降本增效，辅助工作和生活？限时报名。

猜你喜欢