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

现在先看看题目。

1.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 .
PROGRAM NAME: pprime
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:cxj6661
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;
}