整數素數和分解：擴展哥德巴赫猜想的遞歸演算法與效能分析

哥德巴赫猜想指出「任意 ≥6 的偶數可寫成兩奇素數之和」。本文將其推廣：輸出一個整數所有「兩個或以上素數之和」的分解式，同構分解（如 2+3 與 3+2）僅保留一種。透過篩法預計算素數表，再以遞歸回溯枚舉所有組合，並附上 C++ 完整實作與大規模測試數據。

演算法架構

1. 篩選素數：CalcPrimes(n) 產出所有 < n 的素數，存入 vector<int>。
2. 遞歸組合：PrintCombinations(剩餘值, 素數表, 起始索引, 目前路徑)
   • 若剩餘值歸零 → 找到一組解，輸出並計數。
   • 從 起始索引 遍歷素數表，確保非遞減序列，自動消除同構重複。
   • 剪枝：素數 > 剩餘值即中斷迴圈。

核心程式碼

void CalcPrimes(int num, vector<int>& primes) {
    primes.clear(); if (num <= 2) return;
    primes.push_back(2);
    for (int i=3; i<num; i+=2) {
        int r = sqrt(i);
        for (int j=2; j<=r; ++j) if (i%j==0) goto next;
        primes.push_back(i);
    next: ;
    }
}

int PrintCombinations(int num, const vector<int>& primes, int from, vector<int>& path) {
    if (num == 0) { /* 輸出 path */ return 1; }
    int cnt = 0;
    for (int i=from; i<primes.size(); ++i) {
        if (num < primes[i]) break;
        path.push_back(primes[i]);
        cnt += PrintCombinations(num - primes[i], primes, i, path);
        path.pop_back();
    }
    return cnt;
}

執行結果摘錄（1~20）

8 = 2+2+2+2 | 2+3+3 | 3+5  (3 種)
10 = 2×5 | 2+2+3+3 | 2+3+5 | 3+7 | 5+5  (5 種)
20 = ... (26 種)

效能基準測試（僅計數，關閉輸出）

效能觀察與優化方向

• 分解數隨 N 指數級增長，N=300 已達 6 億種，純遞歸回溯屬指數複雜度，難以繼續擴展。
• 可引入 動態規劃（DP）：dp[i][j] 表示用前 j 個素數湊出 i 的方案數，將複雜度降至 O(N × π(N))。
• 若需列舉具體分解式，可結合 記憶化搜尋 + 生成器模式 按需產出，避免一次性爆記憶體。

「素數分解問題既是經典數論練習，也是遞歸與 DP 思維轉換的絕佳教材。」