[USACO][Section 1.5][搜索] Superprime Rib

题目大意：

给出一个整数n，要求输出所有n位超级质数。超级质数的定义为，一个“依次去掉最右边一位后依然为质数”的质数。

思路：

一个n位质数去掉最右边一位依然为质数，说明其一定从n-1位质数演变而来。通过广搜按位数从小到大的顺序搜索到第n位即可。

代码：

/*
ID: lujunda1
LANG: C++
PROG: sprime
*/
#include
#include
#include
#include
using namespace std;
bool prime(int n)
//判断参数n是否为素数。 
{
    if(n<2)
        return false;
    for(int i=2;i<=sqrt(double(n));i++)
        if(n%i==0)
            return false;
    return true;
}
int bfs(int n)
//搜索n位超级质数。 
{
    queue q;
    q.push(0);
    int temp=0;
    while(temp++<n)
    {
        int size=q.size();
        while(size--)
        {
            int head=q.front();
            q.pop();
            if(n==1)
                printf("2\n");
            if(temp==1&&n!=1)
                q.push(2);
            for(int i=1,son;i<10;i+=2)
            //除2以外，所有质数都是奇数，所以只搜奇数并对2做特殊处理即可。 
            {
                son=head*10+i;
                if(prime(son))
                    if(temp==n)
                    //若是n位数便直接输出。 
                        printf("%d\n",son);
                    else
                    //不是n位数便压入队列。 
                        q.push(son);
            }
        }
    }
}
int main()
{
    freopen("sprime.in","r",stdin);
    freopen("sprime.out","w",stdout);
    int n;
    scanf("%d",&n);
    bfs(n);
}