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

#include <iostream>      // 输入输出流
#include <string>        // 字符串处理
#include <vector>        // 动态数组 vector
#include <algorithm>     // reverse 函数需要
using namespace std;

using ll = long long;
const int MAX_SUM = 900000; // 最大可能的数位和：每位最大是9，最多100000位，9*100000=900000

vector<bool> is_prime; // is_prime[i] = true 表示 i 是质数

// 预处理所有小于等于 MAX_SUM 的质数，使用埃氏筛法
void init_prime() {
    is_prime.assign(MAX_SUM + 1, true); // 先假设所有数都是质数
    is_prime[0] = is_prime[1] = false;  // 0 和 1 不是质数
    for (int i = 2; i * i <= MAX_SUM; ++i) {
        if (is_prime[i]) { // 如果 i 是质数
            // 把 i 的倍数标记为非质数
            for (int j = i * i; j <= MAX_SUM; j += i) {
                is_prime[j] = false;
            }
        }
    }
}

// 计算一个大整数（字符串表示）各位数字之和
int digit_sum(const string &s) {
    int sum = 0;
    for (char c : s) {
        sum += c - '0'; // 把字符 '0'~'9' 转成对应数字并累加
    }
    return sum;
}

// 字符串表示的大整数加1，模拟加法
string add_one(const string &s) {
    string res = s;
    int n = res.size();
    int carry = 1; // 初始进位为1，相当于 +1 操作
    for (int i = n - 1; i >= 0 && carry; --i) {
        int num = res[i] - '0' + carry;  // 当前位 + 进位
        res[i] = (num % 10) + '0';       // 更新当前位
        carry = num / 10;                // 更新进位
    }
    if (carry) {
        res = '1' + res; // 如果最高位还有进位，比如 999 + 1 = 1000
    }
    return res;
}

// 比较两个字符串大整数的大小，判断 a <= b
bool my_less_equal(const string &a, const string &b) {
    if (a.size() != b.size()) 
        return a.size() < b.size(); // 位数少的一定小
    return a <= b; // 位数相等时按字典序比较（因为每位都是0-9）
}

// 字符串大整数乘以2，模拟乘法
string multiply_by_two(const string &s) {
    string res;
    int carry = 0;
    for (int i = s.size() - 1; i >= 0; --i) {
        int num = (s[i] - '0') * 2 + carry; // 当前位*2 + 进位
        res.push_back((num % 10) + '0');    // 保存个位
        carry = num / 10;                   // 更新进位
    }
    if (carry) {
        res.push_back(carry + '0'); // 如果最后还有进位
    }
    reverse(res.begin(), res.end()); // 结果是逆序的，需要反转
    return res;
}

// 每组数据的处理逻辑
void solve() {
    string x;
    cin >> x;
    string limit = multiply_by_two(x); // 计算 2x，作为上界

    string now = x; // 从 x 开始枚举
    while (my_less_equal(now, limit)) { // 只要 now <= 2x
        int sum = digit_sum(now); // 计算 now 的数位和
        if (is_prime[sum]) {       // 如果数位和是质数
            cout << now << '\n';   // 输出答案
            return;
        }
        now = add_one(now); // 否则枚举下一个数 now+1
    }
    cout << -1 << '\n'; // 如果没找到，输出 -1
}

int main() {
    ios::sync_with_stdio(false); // 提高 cin/cout 效率
    cin.tie(nullptr);            // 取消 cin 与 cout 的绑定

    init_prime(); // 预处理质数信息

    int T;
    cin >> T;     // 多组数据
    while (T--) {
        solve();
    }

    return 0;
}