哥德巴赫猜想（升级版）(Ternary Goldbach Conjecture) 题解

思路分析

先用素数筛预处理 $2 \sim 20000$ 内的所有质数。为了保证字典序最小（第一个质数最小，其次第二个质数最小），从 $2$ 开始从小到大枚举第一个质数 $p_1$（切勿漏掉偶质数 $2$！例如 $11 = 2 + 2 + 7$），再从 $p_1$ 开始从小到大枚举第二个质数 $p_2$，令 $p_3 = n - p_1 - p_2$：一旦满足 $p_3 \ge p_2$ 且 $p_3$ 为质数，立即输出 p1 p2 p3 并结束程序。

参考代码

#include <iostream>
using namespace std;

const int MX = 20005;
bool notPrime[MX];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    notPrime[0] = notPrime[1] = true;
    for (int i = 2; i * i <= n; ++i)
    {
        if (!notPrime[i])
        {
            for (int j = i * i; j <= n; j += i) notPrime[j] = true;
        }
    }
    for (int p1 = 2; p1 <= n; ++p1)
    {
        if (notPrime[p1]) continue;
        for (int p2 = p1; p1 + p2 + p2 <= n; ++p2)
        {
            if (notPrime[p2]) continue;
            int p3 = n - p1 - p2;
            if (!notPrime[p3])
            {
                cout << p1 << " " << p2 << " " << p3 << "\n";
                return 0;
            }
        }
    }
    return 0;
}