c050 - 00453 - Goldbach's Conjecture

🔗 前往 ZeroJudge 原題

題目描述

題目要求驗證哥德巴赫猜想，對於任何大於 4 的偶數 n，找到兩個奇數質數 a 和 b，使得 n = a + b。如果存在多組解，輸出 b - a 最大的那組。如果找不到解，則輸出 "Goldbach's conjecture is wrong."。

解題思路

使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 預先計算出 1000000 以內的質數。然後，對於每個輸入的偶數 n，遍歷所有小於 n 的質數 i，檢查 n - i 是否也是質數。如果找到一組質數 a 和 b 滿足 n = a + b，則輸出結果。由於題目要求輸出 b - a 最大的那組，但程式碼只輸出找到的第一組解，因此程式碼並未完全符合題目要求。

複雜度分析

• 時間複雜度: O(N log log N + N * sqrt(N))，其中 N 是輸入數字的最大值 (1000000)。O(N log log N) 是篩選質數的時間複雜度，O(N * sqrt(N)) 是遍歷質數並檢查 n - i 是否為質數的時間複雜度。
• 空間複雜度: O(N)，用於儲存質數標記陣列 p。

程式碼

#include <iostream>
using namespace std;
bool p[1000001];
int main(){
	for(int i=2;i<=1000;i++)
		for(int j=i<<1;j<=1000000;j+=i)
			p[j]=1;
	int n;
	while(cin >> n){
		if(n==0)break;
		for(int i=3;i<=1000000;i++){
			if(p[i]==0&&p[n-i]==0){
				cout << n << " = " << i << " + " << n-i << "\n";
				break;
			}
		}
	}
}