题解 | 小红的“质数”寻找

#include <bits/stdc++.h>
using namespace std;
bool check(int num){
    if(num == 1)
        return false;
    for(int i = 2; i <= sqrt(num); ++i){
        if(num % i == 0)
            return false;
    }
    return true;
}
int sum(long long num){
    int result = 0;
    while(num > 0){
        int r = num % 10;
        result += r;
        num = num / 10;
    }
    return result;
}
int main() {
    int T;
    cin>>T;
    while(T--){
        char x[1000008];
        cin>>x;
        int min = 0, max = 0;
        int length = 0;
        for(int i = 0; x[i] != '\0'; ++i){
            if(i == 0 && x[i + 1] != '\0'){
                min = x[i] - '0' + 1;
                if((x[i] - '0') * 2 >= 10){
                    max += 9;
                }else max += (x[i] - '0') * 2 - 1; 
            }else if(i == 0){
                min = x[i] - '0';
                max = (x[i] - '0') * 2;
            }else{
                max += 9;
            }
            if(x[i + 1] == '\0')
                length = i + 1;
        }
        int flag = 0;
        for(long long i = min; i <= max; ++i){
            if(check(i))
                {
                    int temp = i;
                    for(int j = 0; j < length; ++j){
                        if(j == 0)
                            {
                                if(length != 1){
                                    cout<<min;
                                    temp -= min;
                                }else{
                                    cout<<temp;
                                }
                            }
                        else {
                            if(temp > 9){
                                cout<<9;
                                temp -= 9;
                            }else {
                                cout<<temp;
                                temp -= temp;
                            }
                        }
                    }
                    cout<<endl;
                    flag = 1;
                    break;
                }
        }
        if(!flag)
            cout<<-1<<endl;
    }
}
// 64 位输出请用 printf("%lld")