多校训练第1轮.G——Goldbach’s conjecture【素数】（哥德巴赫猜想）

题目传送门

题意

• 求哥德巴赫猜想

题解

• 数据范围 $1e9$
• 不能打表，直接暴力搜就可以
• 分析复杂度：考虑素数分布：$O(\frac{n}{logn})$。不太严谨地近似为随机分布，则可以认为枚举成功的概率是
  $O(\frac{1}{lo{g}^{2}n})$ 的。因此就算暴力判断跑得很满，也是 $O(\frac{\surd n}{lo{g}^{2}n})$ 的。
  实测 $10^9$ 以内最小表示最大的偶数是 721013438 = 1789 + 721011649。

AC-Code

#include <iostream>
#include <vector>
#include <cstring>using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 1e6;bool IsPrime(int x) {
     // if (x <= 1)	return false;if (~x & 1 || x % 3 == 0)	return x <= 3; // 取反末尾是1说明是偶数for (int i = 5, j = 2; i * i <= x; i += j, j = j == 2 ? 4 : 2)if (x % i == 0)	return false;return true;
}
int main() {
    int n;	while (cin >> n) {
    if (n == 4) {
    cout << "2 2" << endl;	continue;}if (IsPrime(n - 3)) {
    cout << 3 << " " << n - 3 << endl;	continue;}for (int i = 5, j = 2; ; i += j, j = j == 2 ? 4 : 2) {
    if (IsPrime(i) && IsPrime(n - i)) {
    cout << i << " " << n - i << endl;	break;}}}}