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;
}

猜你喜歡