思路与算法

枚举较小加数a从2到floor(S/2)，另一个数固定为S-a。用试除法检查两者是否为素数；若均为素数，更新最大乘积。题目保证有解，输出最终最大值。

正确性说明

试除到平方根能够找到任意合数因子对中的较小者，因此素数判定准确。每对和为S的素数都能按a不大于b排列，此时a必在枚举区间，所以合法候选无遗漏。每次更新都来自合法数对，遍历后的最大值就是最优乘积。

复杂度

候选O(S)对，每对两次试除各O(sqrt(S))，总时间O(S sqrt(S))，额外空间O(1)，best初始化O(1)。S不超过10000，乘积不超过S²/4=25000000，int足够。

易错点

允许两个质数相同，如4=2+2；奇数也可能有解，如5=2+3。不能只检查S/2是否为素数，应枚举所有候选。输出乘积而非数对。声明保证有解，因此所有测试均检查存在素数拆分，不加入无解11。

参考代码（C++11）

#include <algorithm>
#include <iostream>
using namespace std;
bool prime(int n) {
    if (n < 2)
        return false;
    for (int d = 2; d * d <= n; ++d)
        if (n % d == 0)
            return false;
    return true;
}
int main() {
    int s;
    cin >> s;
    int best = 0;
    for (int a = 2; a <= s / 2; ++a)
        if (prime(a) && prime(s - a))
            best = max(best, a * (s - a));
    cout << best << '\n';
}