AcWing 4520：质数 ← BFS

【题目来源】
https://www.acwing.com/problem/content/4523/

【题目描述】
给定一个正整数 X，请你在 X 后面添加若干位数字（至少添加一位数字；添加的数不能有前导0），使得结果为质数，在这个前提下所得的结果应尽量小。

【输入格式】
第一行包含一个整数 T，表示共有 T 组测试数据。
每组数据占一行，包含一个整数 X。

【输出格式】
每组数据输出一行结果，一个整数，表示所得的满足条件的最小质数。

【数据范围】
1≤T≤100，
1≤X≤100。

【输入样例】
1
1

【输出样例】
11

【算法代码】

#include <bits/stdc++.h>
using namespace std;bool flag;bool is_prime(int x) {for(int i=2; i*i<=x; i++) {if(x%i==0) return false;}return true;
}void bfs(int x) {queue<int> q;for(int i=1; i<=9; i++) {q.push(x*10+i);}while(!flag) {int t=q.front();q.pop();if(is_prime(t)) {flag=true;cout<<t<<endl;}for(int i=1; i<=9; i++) {q.push(t*10+i);}}
}int main() {int T;cin>>T;while(T--) {int x;cin>>x;flag=false;bfs(x);}return 0;
}/*
in:
1
1out:
11
*/

【参考文献】
https://www.acwing.com/solution/content/126885/
https://www.acwing.com/solution/content/126522/