Baudelaire is Programmer

在解决PackingRectangles这个问题的时候我强调枚举时要“将粗暴进行到底”，但并不是说可以无限度“粗暴”，当粗暴会导致TLE时，适当地构造解空间往往能大大优化程序的执行时间。

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 .

区间上限是1亿，如果我们直接枚举所有数据并检验是否是回文和素数会超时，实际上我们可以先构造出所有的回文数再检测他们是否是素数，n以内的回文数是很稀疏的，构造回文时我们只需枚举各个数位就可以了，这可以用o(√n)时间完成，另外检测n是否是素数的时间是o(√n)，所以我们得到了一个o(n)的方法。

进化：

通过PackingRectangles和此问题，我们涉及到了构造和枚举的问题，过度构造会增加编程的复杂度，过度枚举又会超时，这就需要贴切的时间分析来选择了。在可接受的时间之内尽量减少构造，保持K.I.S.S（keep it simple and stupid）原则是个很好的方法。

点击查看我的程序源码：

/*
ID: *******
LANG: C++
TASK: pprime
*/
#include<stdio.h>
#include<stdlib.h>

int a,b;
FILE *fin,*fout;

typedef struct{
	int digital[9];
}Num;

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

void createPalinAndTest(int n,int L,Num num){//构造长度L的回文数
	int i;
	if(L%2==0&&n>L/2 || L%2==1&&n>L/2+1){
		//利用前一半构造整个回文数并且检测是否是素数
		for(i=n;i<=L;i++)
			num.digital[i-1]=num.digital[1+L-i-1];
		int t=1,N=0;
		for(i=0;i<L;i++){
			N+=t*num.digital[i];
			t*=10;
		}
		if(N<=b&&N>=a&&isPrime(N)){
			fprintf(fout,"%d\n",N);
		}
		return;
	}
	for(i=0;i<=9;i++){
		if(n==1&&i==0)continue;//首位不得为0
		num.digital[n-1]=i;
		createPalinAndTest(n+1,L,num);
	}
	return;
}

int main(){
	fin=fopen("pprime.in","r");
	fout=fopen("pprime.out","w");
	fscanf(fin,"%d %d",&a,&b);
	int i;
	Num num;
	for(i=1;i<=8;i++)
		createPalinAndTest(1,i,num);
	return 0;
}