543 Goldbach's Conjecture

題目連結

題目敘述

1742 年，德國業餘數學家 Christian Goldbach 寄了一封信給 Leonhard Euler，在信中提出了以下的猜想：
所有大於 2 的數字都可以寫成三個質數的總和
Goldbach 當時將 1 視為質數，但這在現今已不再被接受。後來，Euler 重新表述了這個猜想為：
所有大於或等於 4 的偶數都可以寫成兩個質數的總和

例如：

8 = 3 + 5
20 = 3 + 17 = 7 + 13
42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23

直到今日，這個猜想是否正確仍未被證明。（喔當然，我是有證明的，但太長了，寫不下在這頁邊緣。）總之，你的任務是驗證 Euler 所表述的哥德巴赫猜想：對所有小於一百萬的偶數進行檢查。

輸入說明

輸入檔將包含一個或多個測試案例

每組測試資料是一個偶數 n，且 6 ≤ n < 1000000。
當 n 為 0 時，代表輸入結束。

輸出說明

對於每組測試案例，輸出一行，格式為 n = a + b，其中 a 與 b 為奇質數
數字與運算符之間應該用一個空格隔開，如下方範例所示
若有多對質數相加為 n，請選擇 b − a 最大的那一對

若無法找到這樣的一對質數，輸出一行 Goldbach's conjecture is wrong.

解題思路

截至目前，強哥德巴赫猜想已被電腦驗證對所有小於 4 × 10¹⁸ 的偶數成立
對於小於 10⁶ 的測資來說，一定會有解
當然，考試時不知道很正常，反正我是忘記寫結果過了ㄏㄏ

有兩種方法

暴力計算從 3 開始枚舉 i 和 n-i 數對是否皆為質數每次枚舉都要重新計算
建質數表隨便一種篩法，把表建起來之後枚舉 i 使得 n-i 也存在於表中的數對

其實測資也不大，有建表跟沒建表時間沒差多少看個人習慣囉

程式碼

暴力計算

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int x) { // 判斷 x 是否為質數
    for (int i = 2; i*i <= x; i++) if (!(x%i)) return 0; // 從 2 到 sqrt(x) 枚舉 i，並檢查 i 是否能整除 x
    return 1;
}

signed main() {
    int n;
    while (cin >> n, n) for (int i = 3; i < n; i++) if (isPrime(i) && isPrime(n-i)) { // 從 3 枚舉到 n-1，若 i 和 n-i 皆為質數，該數對即為答案
        cout << n << " = " << i << " + " << n-i << '\n';
        break;
    }
}

建質數表

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define N 1000000+1

signed main() {
    vector<int> p(N, 1), ps; p[0] = p[1] = 0;
    for (int i = 2; i < N; i++) if (p[i]) for (int j = i*i; j < N; j += i) p[j] = 0; // 埃篩建表
    for (auto &i : p) if (i) ps.push_back(&i-p.data()); // 將質數放進一向量中

    int n;
    while (cin >> n, n) for (auto &i : ps) if (p[n-i]) { // 若 i 和 n-i 都在質數向量中，該數對即為答案
        cout << n << " = " << i << " + " << n-i << '\n';
        break;
    }
}