深搜？广搜！（题解2）

纯原创qwq

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
struct node{
	int val, step;
};
queue <node> q;//队列 
int a[100005];
bool check(int x){//判断质数 
	if(x < 2) return 0;
	if(x == 2) return 1;
	for(int i = 2; i * i <= x; i++){
		if(x % i == 0) return 0;
	}return 1;
}
void bfs(int n){//广搜 
	q.push({0, 0});
	while(!q.empty()){
		node head = q.front();//取最前面的 
		q.pop();
		if(head.step == n){
			printf("%d\n", head.val);//如果满足条件，输出 
			continue;
		}
		for(int i = 0; i <= 9; i++){
			int x = head.val * 10 + i;//多加一位 
			if(check(x)){
				q.push({x, head.step + 1});//是质数就进队列 
			}
		}
	}
}
int main(){
	int n;
	cin >> n;
	bfs(n);

	return 0;
}