解题思路

哥德巴赫猜想说，任何一个大于 9 的奇数都能拆成三个素数之和。题目要求把给定的奇数 a 的所有拆法找出来。

思路：

1. 先写一个判断质数的函数 zs(x)
2. 枚举前两个加数 i 和 j，第三个加数就是 a-i-j
3. 检查三个数是否都是质数
4. 还要保证 i ≤ j ≤ a-i-j，这样三个数从小到大排，不会重复
5. 先统计一共有多少种解并输出，再输出每个解

为什么枚举两个数就够了？ 因为总和是固定的 a，前两个数定了，第三个就自动确定了。

为什么要 i ≤ j ≤ a-i-j？ 比如 15=2+2+11 和 15=11+2+2 其实是同一种拆法。加上从小到大排序的条件，就只会输出一次。

举例 a=15：

• 2+2+11、3+5+7、5+5+5 三种，输出 3 个解

参考代码

#include <iostream>
using namespace std;

bool zs(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() {
    int a, s = 0;
    cin >> a;

    // 先统计解的个数
    for (int i = 2; i < a; i++) {
        for (int j = 2; j < a; j++) {
            if (zs(i) && zs(j) && zs(a - i - j) && i <= j && j <= a - i - j) {
                s++;
            }
        }
    }
    cout << s << endl;

    // 再输出每个解
    for (int i = 2; i < a; i++) {
        for (int j = 2; j < a; j++) {
            if (zs(i) && zs(j) && zs(a - i - j) && i <= j && j <= a - i - j) {
                cout << a << "=" << i << "+" << j << "+" << a - i - j << endl;
            }
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(N²√N)，双重枚举加质数判断
• 空间复杂度：O(1)