哥德巴赫猜想分布有个特性，那就是最小素数小于$10000$的个数几乎为零。这个性质是什么结果呢？那就是从一开始历遍找到第一个同时满足isprime(p) && isprime(n-p)的数$\ p\$非常小。根据米勒拉宾算法，可以很快校验一个质数，这样对$\ n-p\$部分的数约等于不用校验。那么实际上需要计算的量非常非常小。

本题需要掌握两个算法:

米勒拉宾算法（至少能快速做到int以内单点素性判断）

Pollard Rho算法详解（题解主要是要对它进行修改）

首先，Pollard rho算法的本质是以Rho形通过生日悖论概率原理提高随机枚举的可靠性。 它不止能够处理素因子分解，这一步只是粗略的功能。更准确地说，它能提高每次随机到的数尽可能地满足素数的性质。

int pollard_rho(int n) {
    // 对n特殊处理，有些初始值是不适合执行pollard rho的，要提前剔除
    // 对于素分解来说，n本身是素数，或者n是2这种就不好。
    // 要知道,一个数如果不是质数，就必然在[2,sqrt(n)]内有因子，或者说有其他素因子。
    loop { // 等价于for(;;)比while true更好的死循环
        int c = Random::randint(1, n - 1);
        auto f = [=](ll x)->int { return (x * x + c) % n; };
        int t = f(0), r = f(f(0));
        while (t != r) {
            int p = g(abs(t - r)); // g是一个将枚举到的一个数映射到解集上的处理。
            if (isprime(p) && isprime(n - p)) return p;
            t = f(t), r = f(f(r));
        }
    }
}

对于素分解来说，特殊处理和g分别是处理非奇素数和素性，然后g取跟n的gcd：

int pollard_rho(int n) {
    if (n == 4) return 2;
    if (isprime(n)) return n;
    loop {
        int c = Random::randint(1, n - 1);
        auto f = [=](ll x)->int { return (x * x + c) % n; };
        int t = f(0), r = f(f(0));
        while (t != r) {
            int p = gcd(abs(t - r), n);
            if (p > 1) return p;
            t = f(t), r = f(f(r));
        }
    }
}

而对于本题来说，两者的差别就是另外的处理了：

int pollard_rho(int n) {
    int mid = n / 2;
    if (isprime(mid)) return mid;
    loop {
        int c = Random::randint(1, n - 1);
        auto f = [=](ll x)->int { return (x * x + c) % n; };
        int t = f(0), r = f(f(0));
        while (t != r) {
            int p = abs(t - r) % mid * 2 + 1;
            if (isprime(p) && isprime(n - p)) return p;
            t = f(t), r = f(f(r));
        }
    }
}

完整代码参考:

#include <bits/stdc++.h>
using namespace std;
typedef __uint128_t ulll;
typedef __int128_t lll;
typedef unsigned long long ull;
typedef long long ll;
#define Unlock
#ifdef DEBUG
#define main_end cout << endl;system("pause");return 0
#else
#define main_end cout << flush;return 0
#endif
#ifdef Unlock
#define main_first ios::sync_with_stdio(false);cin.tie(nullptr)
#else
#define main_first cin.tie(nullptr)
#endif
#define gcd __gcd
#define count_bits __builtin_popcountll
#define lowbit __builtin_ctzll
#define log2n __builtin_clzll
#define loop for(;;)
constexpr ll mpow(ll z, ll y, ll m) {
    ll ans = 1;
    for (;y;y >>= 1, z = z * z % m)
        if (y & 1)ans = ans * z % m;
    return (ll)ans % m;
}
namespace Random {
    mt19937_64 r(chrono::system_clock::now().time_since_epoch().count());
    int randint(int L, int R) {
        return uniform_int_distribution<int>(L, R)(r);
    }
}
const int witness[] = { 2, 7, 61 };
bool isprime(int n) {
    if (n < 2) return false;
    int r = n / ((n - 1) & (1 - n));
    for (int w : witness) {
        if (n % w == 0) return n == w;
        if (mpow(w, r, n) != 1) {
            for (;r < n;r <<= 1) if (mpow(w, r, n) == n - 1) break;
            if (r >= n) return false;
        }
    }
    return true;
}
int pollard_rho(int n) {
    int mid = n / 2;
    if (isprime(mid)) return mid;
    loop {
        int c = Random::randint(1, n - 1);
        auto f = [=](ll x)->int { return (x * x + c) % n; };
        int t = f(0), r = f(f(0));
        while (t != r) {
            int p = abs(t - r) % mid * 2 + 1;
            if (isprime(p) && isprime(n - p)) return p;
            t = f(t), r = f(f(r));
        }
    }
}
int main() {
    main_first;
    int t; cin >> t;
    for (;t;--t) {
        int n; cin >> n;
        int p = pollard_rho(n);
        cout << p << ' ' << n - p << '\n';
    }
    main_end;
}

pollard_rho 是优秀的随机数论分解算法，还有带Floyd判环算法的再优化版本，具体参考：Pollard Rho算法详解。

pollard_rho一般都依赖于isprime的性能，这里采用前面提及的米勒拉宾算法来快速计算，因此可以实现1e9甚至更大范围的哥德巴赫分解。