USACO Section 1.5 Prime Palindromes

/*
ID: lucien23
PROG: pprime
LANG: C++
*/

#include<iostream>
#include<fstream>
#include<set>
#include<cmath>
#include<string>
#include<sstream>
#include<algorithm>
using namespace std;

set<int> primes;//10000以内的素数
bool isPalindrome(int num);
bool isPrime(int num);

int main()
{
	ifstream infile("pprime.in");
	ofstream outfile("pprime.out");
	if(!infile || !outfile)
	{
		cout<<"file operation failure!"<<endl;
		return -1;
	}

	int a,b;
	infile>>a>>b;
	set<int> pprimes;
	/*
	 *可能既为质数又是回文数的
	 *必然是5或者以1,3,7,9结尾的数
	 */
	//筛选出10000以内的素数
	for (int i=2;i<=10000;i++)
	{
		primes.insert(i);
	}
	for (int i=2;i<=100;i++)
	{
		int num=i*2;
		while(num<=10000)
		{
			primes.erase(num);
			num+=i;
		}
	}
	
	set<int> palindromes;
	//产生回文
	if(a<10)
	{//产生1位数的回文
		palindromes.insert(5);
		palindromes.insert(7);
		palindromes.insert(9);
	}
	if(b>10)
	{//产生2位数的回文
		palindromes.insert(11);
	}

	if(b>100)
	{//产生3位数的回文
		for (int i=1;i<=9;i++)
		{
			if(i%2==0 || i==5)
				continue;
			for (int j=0;j<=9;j++)
			{
				palindromes.insert(i*100+j*10+i);
			}
		}
	}

	if(b>10000)
	{//产生5位数的回文
		for (int i=1;i<=9;i++)
		{
			if(i%2==0 || i==5)
				continue;
			for (int j=0;j<=9;j++)
			{
				for (int k=0;k<=9;k++)
				{
					palindromes.insert(i*10000+j*1000+k*100+j*10+i);
				}
			}
		}
	}

	if(b>1000000)
	{//产生7位数的回文
		for (int i=1;i<=9;i++)
		{
			if(i%2==0 || i==5)
				continue;
			for (int j=0;j<=9;j++)
			{
				for (int k=0;k<=9;k++)
				{
					for (int m=0;m<=9;m++)
					{
						palindromes.insert(i*1000000+j*100000+k*10000+m*1000+k*100+j*10+i);
					}
				}
			}
		}
	}

	//判断是否为素数
	for (set<int>::iterator it=palindromes.begin();it!=palindromes.end();it++)
	{
		if(*it>=a && *it<=b && isPrime(*it))
		{
			pprimes.insert(*it);
		}else if(*it>b){
			break;
		}
	}

	for(set<int>::iterator it=pprimes.begin();it!=pprimes.end();it++)
	{
		outfile<<*it<<endl;
	}

	return 0;
}

bool isPrime(int num)
{
	if(primes.find(num)!=primes.end())
		return true;
	int temp=sqrt((double)num);
	for(set<int>::iterator it=primes.begin(); *it<=temp && it!=primes.end(); it++){
		if(num%*it==0)
			return false;
	}
	return true;
}

USACO Section 1.5 Prime Palindromes,布布扣,bubuko.com

USACO Section 1.5 Prime Palindromes

原文：http://blog.csdn.net/lucienduan/article/details/21482343