杭电ACM1431——素数回文~击表法

杭电ACM1431——素数回文~~打表法

如题目，求a 到 b 之间的回文素数。b最大为10^8。

暴力的方法，会超时，所以求素数用埃式筛选法。

由于筛选10^8之间的素数，也会超时，所以，为了降低所需的时间，就用暴力的方法算出最大的回文素数为9989899。所以，我们只需要找10^7之间的素数，然后根据素数表，找出是回文的素数。

下面的是AC的代码：

#include <iostream>
#include <cstring>
using namespace std;

const int Max = 10000000;

int prime[1000000];
int ans[10000];
bool is_prime[Max];
int p = 0;

void getPrime()               //找出素数放在数组prime中
{
	int i, j;
	memset(is_prime, true, sizeof(is_prime));
	is_prime[0] = is_prime[1] = false;
	for(i = 2; i < Max; i++)
	{
		if(is_prime[i])
		{
			prime[p++] = i;
			for(j = 2 * i; j < Max; j += i)
				is_prime[j] = false;
		}
	}
}

int isIt(int a)          //判断回文
{
	int x = a;
	int y = 0;
	while(x > 0)
	{
		y = y * 10 + x % 10;
		x /= 10;
	}
	if(y == a)
		return 1;
	else
		return 0;
}

int main()
{
	int a, b, i, j = 0;
	getPrime();
	for(i = 0; i < p; i++)             //找出回文素数，放在ans数组中
		if(isIt(prime[i]))
			ans[j++] = prime[i];
	while(cin >> a >> b)
	{
		for(i = 0; i < j; i++)
		{
			if(a > ans[i])
				continue;
			else if(ans[i] <= b)
				printf("%d\n", ans[i]);
			else
				break;
		}
		printf("\n");
	}
	return 0;
}