解题思路

题目要求把一个数字串拆成两段，使两段之和是最小的素数。

比如 13304：

• 1+3304=3305（不是素数）
• 13+304=317（素数）
• 133+04=137（素数，且最小）
• 1330+4=1334（不是素数）

方法：

1. 枚举所有分割位置
2. 把左右两段转成整数相加
3. 判断和是不是素数
4. 记录最小的素数
5. 如果没有素数输出 -1

参考代码

#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return false;
    }
    return true;
}

int main() {
    string s;
    cin >> s;

    int ans = -1;

    for (int pos = 1; pos < s.size(); pos++) {
        string left = s.substr(0, pos);
        string right = s.substr(pos);
        int a = atoi(left.c_str());
        int b = atoi(right.c_str());
        int sum = a + b;

        if (isPrime(sum)) {
            if (ans == -1 || sum < ans) {
                ans = sum;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，N 为数字串长度，素数判断 O(√sum)
• 空间复杂度：O(1)