分析

• 一种做法是对于每个需要分解的数t，我们可以从3开始遍历，然后判断两个数是否是质数，如果是的话，输出答案，考虑下一个数。这样的时间复杂度是：$O(n \times \sqrt n)$的，会超时，因此不可采取。

• 我们可以首先使用线性筛法将所有的质数筛选出来，对于某个需要分解的数t，从a=3开始遍历这些质数，然后判断t-a是否是质数，如果是的话输出答案，继续处理下一个数据。

• 如何判断t-a是否是质数呢？这个可以采取查表的方式进行，在线性筛法中会使用到st数据，表示是否被筛掉，如果st[t-a]==false的话说明t-a是质数。

• 计算量分析：因为n最大取$10^6$，根据质数定理，1~n中大约有$\frac{n}{ln n}$个质数，假设有T组数据，则计算量为$10^6 + T \times \frac{10^6}{ln(10^6)} \approx 10^6 + 50000 \times T$。完全可以接受。

代码

#include <iostream>

using namespace std;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

void init(int n) {

    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {

    init(N - 1);

    int n;
    while (cin >> n, n) {
        for (int i = 1; ; i++) {  // primes[1] = 3, 从3开始
            int a = primes[i];
            int b = n - a;
            if (!st[b]) {
                printf("%d = %d + %d\n", n, a, b);
                break;
            }
        }
    }

    return 0;
}