d307 - 00686 - Goldbach's Conjecture (II)

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定偶數 n (4 <= n < 215) 可以表示為兩個質數之和的不同組合數。需要注意的是，(p1, p2) 和 (p2, p1) 被視為相同的組合。

解題思路

此題的核心思路是預先計算所有小於 32768 的質數，並使用它們來計算每個偶數 n 可以表示為兩個質數之和的組合數。

1. 質數篩選: 使用埃拉托斯特尼篩法 (Sieve of Eratosthenes) 找出小於 32768 的所有質數。
2. 組合計算: 遍歷所有質數的配對，計算它們的和。如果和 k 小於 32768，則將 ans[k] 的計數器加 1。由於我們只計算 i <= j 的配對，因此避免了重複計算 (p1, p2) 和 (p2, p1) 的情況。
3. 查詢輸出: 讀取輸入的偶數 n，並輸出預先計算好的 ans[n] 值。

複雜度分析

• 時間複雜度: O(N log log N + N^2)，其中 N 是 32768。O(N log log N) 是埃拉托斯特尼篩法的時間複雜度，O(N^2) 是計算質數配對和的複雜度。
• 空間複雜度: O(N)，用於儲存質數陣列 p 和組合計數陣列 ans。

程式碼

#include <iostream>
using namespace std;
int p[3513],it=0,ans[33000];
bool prime[33000]={1,1};
int main() {
    for(int i=2;i<=182;++i)
        if(!prime[i])
            for(int j=i+i;j<32768;j+=i)
                prime[j]=1;
    for(int i=2;i<32768;++i)
    	if(!prime[i]){
    		p[it]=i;
    		++it;
		}
	for(int i=0;i<it;++i)
		for(int j=i;j<it;++j){
			int k=p[i]+p[j];
			if(k<32768)
				++ans[k];
		}
    int n;
    while (cin >> n){
        if (n==0)break;
        cout << ans[n] << "\n";
    }
    return 0;
}