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

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 900010; // 数位和最大值附近
bitset<MAXN> isPrime;    // 标记质数

// 预处理质数
void sieve() {
    isPrime.set();          // 全部初始化为 1
    isPrime[0] = isPrime[1] = 0; // 0 和 1 不是质数
    for (long long i = 2; i < MAXN / i; i++) {
        if (isPrime[i]) {
            for (long long j = i * i; j < MAXN; j += i) {
                isPrime[j] = 0; // 标记非质数
            }
        }
    }
}

// 计算数位和
int digitSum(const string& s) {
    int sum = 0;
    for (char c : s) {
        sum += c - '0';
    }
    return sum;
}

// 将字符串表示的数加1
string increment(string s) {
    int n = s.size();
    string res = s;
    bool carry = true;
    for (int i = n - 1; i >= 0 && carry; i--) {
        int digit = res[i] - '0' + 1;
        res[i] = (digit % 10) + '0';
        carry = digit >= 10;
    }
    if (carry) res = '1' + res;
    return res;
}

// 寻找满足条件的数
string findNumber(const string& x) {
    // 计算 2x
    string doubleX = x;
    int carry = 0;
    for (int i = doubleX.size() - 1; i >= 0; i--) {
        int digit = (doubleX[i] - '0') * 2 + carry;
        doubleX[i] = (digit % 10) + '0';
        carry = digit / 10;
    }
    if (carry) doubleX = '1' + doubleX;

    // 从 x+1 开始检查
    string curr = increment(x);
    while (curr.size() < doubleX.size() || (curr.size() == doubleX.size() && curr <= doubleX)) {
        if (isPrime[digitSum(curr)]) {
            return curr;
        }
        curr = increment(curr);
    }

    // 如果 [x+1, 2x] 内没有找到，检查 x 本身
    if (isPrime[digitSum(x)]) {
        return x;
    }
    return "-1";
}

int main() {
    sieve(); // 预处理质数
    int T;
    cin >> T;
    for (int t = 0; t < T; t++) {
        string x;
        cin >> x;
        string result = findNumber(x);
        cout << result << endl;
    }
    return 0;
}