抛砖引玉

题目背景

类以诱之，击蒙也。

题目描述

刘老师 认为质数是玉。

现在他给你一个不包含数位 00 的整数 nn，请你看看能否通过重新排列数位来把这个整数变为质数。

如果可以，输出可以变成的最小的一个质数，否则输出 −1−1。

输入格式

一个数 nn。

输出格式

输出重排数位（也可以不重排）可以变成的最小的一个质数，如果变不成质数，输出 −1−1。

输入数据 1

772

Copy

输出数据 1

277

Copy

实际上 277,727277,727 都是质数，输出较小的就是 277277。

输入数据 2

277

Copy

输出数据 2

277

Copy

可以不重排，如果初始就是质数。

输入数据 3

248

Copy

输出数据 3

-1

Copy

不管怎么重排都不是质数。

数据规模与约定

对于 100%100% 的数据，1≤n<1061≤n<106，且 nn 不含数位 00。

• 子任务 1（10 分）：保证怎么排都不是质数。（但想必不会有人第一题只输出 −1−1 拿 1010 分吧。）
• 子任务 2（30 分）：保证 n<20n<20。
• 子任务 3（40 分）：保证 nn 是个三位数。
• 子任务 4（20 分）：没有特殊限制。

题解：

#include<bits/stdc++.h>
using namespace std;
bool ss(int n){
	if(n<2) return 0;
	for(int i=2;i<=sqrt(n);i++){
		if(n%i==0) return 0;
	}
	return 1;
} 
int main() {
    //freopen("pao.in","r",stdin);
    //freopen("pao.out","w",stdout);
    int n;
    cin >> n;
    vector<int> d;
    int t = n;
    while (t > 0) {
        d.push_back(t % 10);
        t /= 10;
    }
    sort(d.begin(), d.end());
    do {
        int num = 0;
        for (int digit : d) {
            num = num * 10 + digit;
        }
        if (ss(num)) {
            cout << num << endl;
            return 0;
        }
    } while (next_permutation(d.begin(), d.end()));
    cout << -1 << endl;
    return 0;
}