USACO Prime Palindromes (pprime)

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