卢俊达

题目大意：

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

思路：

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

代码：

/*
ID: lujunda1
LANG: C++
PROG: sprime
*/
#include<iostream>
#include<stdio.h>
#include<cmath>
#include<queue>
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<int> 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);
}