题解 | #查找组成一个偶数最接近的两个素数# 先筛素数，再从中间向两边查找

优化1

我们可以预处理出来一个小于n的素数数组，而不必每次去判断是否为素数。

优化2

从素数数组中间向两边查找，时间一定是最短的

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 1010;
bool st[N];

inline void solve(int &n)
{
    vector<int> pr;
    for (int i = 2; i <= n; i++) {
        if (!st[i]) {
            pr.push_back(i);
            for (int j = i; j <= n; j += i)
                st[j] = true;
        }
    }
    //for (int i = 0; i < pr.size(); i++) cout << i << '-' << pr[i] << '|';
    //cout << endl;
    int mid = n >> 1;
    int k = -1;
    for (int i = 0; k == -1 && i < pr.size() - 1; i++) {    // find middle index
        if (pr[i] <= mid && pr[i + 1] > mid) k = i;
    }
    //cout << k << endl << pr[k];
    //return;
    int i = k, j = k;
    for (; i >= 2 && j < n;) {
        if (pr[i] + pr[j] == n) break;
        else if (pr[i] + pr[j] < n) j++;
        else i--;
    }
    cout << pr[i] << endl << pr[j] << endl;
}

int main()
{
    int n;
    for (; cin >> n; memset(st, false, sizeof(st)))
        solve(n);
    return 0;
}