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
1

out:
11
*/

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