USACOPrime Palindromes

http://ace.delos.com/usacoprob2?a=SFbMUjuLYE9&S=pprime

额。。。用了一种很笨的方法，速度极慢==

首先这里不能先求素数再求回文，时间上肯定过不了。

要先生成回文数，再判断是否为素数。

我的方法：直接枚举回文数的前半部分，然后把数扩展成回文数，判断是否为质数。

主要步骤：

1.筛法求出10000以内的素数，在后面的素数判断中可以加快速度

2.枚举回文数的前半部分，当然这前半部分也要判断是否为回文素数

3.把前半部分扩展成一个完整的回文数，判断是否为素数

4.输出

如果用5层循环直接枚举数位上的数，然后直接扩展成回文数，这样就不用把数拆来拆去了，估计速度上快很多

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;

int a,b;
int rr[100000]={0},ss=0;

bool f[10005]={0};
int prime[2000],sum=0;
void sushu()         //筛法求10000以内的素数
{
    f[1]=true;
    for (int i=2;i<=5000;i++)
    if (!f[i])
    {
        int j=2;
        while (i*j<=10000)
        {
            f[i*j]=true;
            j++;
        }
    }
    for (int i=2;i<=10000;i++)
    if (!f[i])
        prime[++sum]=i;
}

bool primee(int x)          //判断x是否为素数
{
    int i=1;
    while (prime[i]<=int(sqrt(x)) && i<=sum)       //原来sqrt函数是定义在math.h中的。。。
    {
        if (x%prime[i]==0) return false;
        i++;
    }
    return true;
}

int temp[10];

void cai(int x,int *temp)       //把x拆开存进temp数组中
{
    int xx=x;
    while (xx>0)
    {
        temp[++temp[0]]=xx%10;
        xx/=10;
    }
}

bool huiwen(int *temp)        //判断回文
{
    int i=1,j=temp[0];
    while(i<j)
    {
        if (temp[i]!=temp[j]) return false;
        i++;j--;
    }
    return true;
}

void kuozan(int *temp,int &x,int &y)        //把回文数的前半部分扩展开，使之变成回文数，注意有两种展开法，就是要注意是奇数展开还是偶数展开
{
    x=0;y=0;
    int i=temp[0];
    while (i>0)
    {
        x=x*10+temp[i];
        i--;
    }
    i=1;
    y=x;
    x=x*10+temp[1];          //偶数展开
    while (i<temp[0])
    {
        i++;
        x=x*10+temp[i];
        y=y*10+temp[i];      //奇数展开
    }
}

void work(int x)
{
    if (x>b) return;

    memset(temp,0,sizeof(temp));
    cai(x,temp);
    if (primee(x) && huiwen(temp) && x>=a)      //有可能本身就是回文素数了
        rr[++ss]=x;
    int xx,yy;
    kuozan(temp,xx,yy);
    if (xx!=x) work(xx);         //递归定义
    if (yy!=x) work(yy);
}

int main()
{
    freopen("pprime.in","r",stdin);
    freopen("pprime.out","w",stdout);
    sushu();
    cin>>a>>b;
    for (int i=1;i<=100000;i++)
        work(i);
    sort(rr+1,rr+ss+1);
    for (int i=1;i<=ss;i++)
        if (rr[i]!=rr[i-1])
            cout<<rr[i]<<endl;
    return 0;
}