【問題描述】
歌德巴赫猜想說任何一個不小於6的偶數都可以分解為兩個奇素數之和。對此問題擴展，如果一個整數能夠表示成兩個或多個素數之和，則得到一個素數和分解式。對於一個給定的整數，輸出所有這種素數和分解式。注意，對於同構的分解只輸出一次（比如5只有一個分解2 + 3，而3 + 2是2 + 3的同構分解式）。
例如，對於整數8，可以作為如下三種分解：
(1) 8 = 2 + 2 + 2 + 2
(2) 8 = 2 + 3 + 3
(3) 8 = 3 + 5
【算法分析】
由於要將指定整數N分解為素數之和，則首先需要計算出該整數N內的所有素數，然後遞歸求解所有素數和分解即可。
C++代碼實現如下：
#include <iostream>
#include <vector>
#include <iterator>
#include <cmath>
using namespace std;
// 計算num內的所有素數（不包括num）
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 root = int(sqrt(i));
int j = 2;
for (j = 2; j <= root; ++j) {
if (i % j == 0)
break;
}
if (j > root)
primes.push_back(i);
}
}
// 輸出所有素數組合(遞歸實現)
int PrintCombinations(int num, const vector<int> &primes, int from, vector<int> &numbers)
{
if (num == 0) {
cout << "Found: ";
copy(numbers.begin(), numbers.end(), ostream_iterator<int>(cout, " "));
cout << '\n';
return 1;
}
int count = 0;
// 從第from個素數搜索，從而避免輸出同構的多個組合
int primesNum = primes.size();
for (int i = from; i < primesNum; ++i) {
if (num < primes[i])
break;
numbers.push_back(primes[i]);
count += PrintCombinations(num - primes[i], primes, i, numbers);
numbers.pop_back();
}
return count;
}
// 計算num的所有素數和分解
int ExpandedGoldbach(int num)
{
if (num <= 3)
return 0;
vector<int> primes;
CalcPrimes(num, primes);
vector<int> numbers;
return PrintCombinations(num, primes, 0, numbers);
}
int main()
{
for (int i = 1; i <= 20; ++i) {
cout << "When i = " << i << ":\n";
int count = ExpandedGoldbach(i);
cout << "Total: " << count << "\n\n";
}
}
運行結果：
When i = 1:
Total: 0
When i = 2:
Total: 0
When i = 3:
Total: 0
When i = 4:
Found: 2 2
Total: 1
When i = 5:
Found: 2 3
Total: 1
When i = 6:
Found: 2 2 2
Found: 3 3
Total: 2
When i = 7:
Found: 2 2 3
Found: 2 5
Total: 2
When i = 8:
Found: 2 2 2 2
Found: 2 3 3
Found: 3 5
Total: 3
When i = 9:
Found: 2 2 2 3
Found: 2 2 5
Found: 2 7
Found: 3 3 3
Total: 4
When i = 10:
Found: 2 2 2 2 2
Found: 2 2 3 3
Found: 2 3 5
Found: 3 7
Found: 5 5
Total: 5
When i = 11:
Found: 2 2 2 2 3
Found: 2 2 2 5
Found: 2 2 7
Found: 2 3 3 3
Found: 3 3 5
Total: 5
When i = 12:
Found: 2 2 2 2 2 2
Found: 2 2 2 3 3
Found: 2 2 3 5
Found: 2 3 7
Found: 2 5 5
Found: 3 3 3 3
Found: 5 7
Total: 7
When i = 13:
Found: 2 2 2 2 2 3
Found: 2 2 2 2 5
Found: 2 2 2 7
Found: 2 2 3 3 3
Found: 2 3 3 5
Found: 2 11
Found: 3 3 7
Found: 3 5 5
Total: 8
When i = 14:
Found: 2 2 2 2 2 2 2
Found: 2 2 2 2 3 3
Found: 2 2 2 3 5
Found: 2 2 3 7
Found: 2 2 5 5
Found: 2 3 3 3 3
Found: 2 5 7
Found: 3 3 3 5
Found: 3 11
Found: 7 7
Total: 10
When i = 15:
Found: 2 2 2 2 2 2 3
Found: 2 2 2 2 2 5
Found: 2 2 2 2 7
Found: 2 2 2 3 3 3
Found: 2 2 3 3 5
Found: 2 2 11
Found: 2 3 3 7
Found: 2 3 5 5
Found: 2 13
Found: 3 3 3 3 3
Found: 3 5 7
Found: 5 5 5
Total: 12
When i = 16:
Found: 2 2 2 2 2 2 2 2
Found: 2 2 2 2 2 3 3
Found: 2 2 2 2 3 5
Found: 2 2 2 3 7
Found: 2 2 2 5 5
Found: 2 2 3 3 3 3
Found: 2 2 5 7
Found: 2 3 3 3 5
Found: 2 3 11
Found: 2 7 7
Found: 3 3 3 7
Found: 3 3 5 5
Found: 3 13
Found: 5 11
Total: 14
When i = 17:
Found: 2 2 2 2 2 2 2 3
Found: 2 2 2 2 2 2 5
Found: 2 2 2 2 2 7
Found: 2 2 2 2 3 3 3
Found: 2 2 2 3 3 5
Found: 2 2 2 11
Found: 2 2 3 3 7
Found: 2 2 3 5 5
Found: 2 2 13
Found: 2 3 3 3 3 3
Found: 2 3 5 7
Found: 2 5 5 5
Found: 3 3 3 3 5
Found: 3 3 11
Found: 3 7 7
Found: 5 5 7
Total: 16
When i = 18:
Found: 2 2 2 2 2 2 2 2 2
Found: 2 2 2 2 2 2 3 3
Found: 2 2 2 2 2 3 5
Found: 2 2 2 2 3 7
Found: 2 2 2 2 5 5
Found: 2 2 2 3 3 3 3
Found: 2 2 2 5 7
Found: 2 2 3 3 3 5
Found: 2 2 3 11
Found: 2 2 7 7
Found: 2 3 3 3 7
Found: 2 3 3 5 5
Found: 2 3 13
Found: 2 5 11
Found: 3 3 3 3 3 3
Found: 3 3 5 7
Found: 3 5 5 5
Found: 5 13
Found: 7 11
Total: 19
When i = 19:
Found: 2 2 2 2 2 2 2 2 3
Found: 2 2 2 2 2 2 2 5
Found: 2 2 2 2 2 2 7
Found: 2 2 2 2 2 3 3 3
Found: 2 2 2 2 3 3 5
Found: 2 2 2 2 11
Found: 2 2 2 3 3 7
Found: 2 2 2 3 5 5
Found: 2 2 2 13
Found: 2 2 3 3 3 3 3
Found: 2 2 3 5 7
Found: 2 2 5 5 5
Found: 2 3 3 3 3 5
Found: 2 3 3 11
Found: 2 3 7 7
Found: 2 5 5 7
Found: 2 17
Found: 3 3 3 3 7
Found: 3 3 3 5 5
Found: 3 3 13
Found: 3 5 11
Found: 5 7 7
Total: 22
When i = 20:
Found: 2 2 2 2 2 2 2 2 2 2
Found: 2 2 2 2 2 2 2 3 3
Found: 2 2 2 2 2 2 3 5
Found: 2 2 2 2 2 3 7
Found: 2 2 2 2 2 5 5
Found: 2 2 2 2 3 3 3 3
Found: 2 2 2 2 5 7
Found: 2 2 2 3 3 3 5
Found: 2 2 2 3 11
Found: 2 2 2 7 7
Found: 2 2 3 3 3 7
Found: 2 2 3 3 5 5
Found: 2 2 3 13
Found: 2 2 5 11
Found: 2 3 3 3 3 3 3
Found: 2 3 3 5 7
Found: 2 3 5 5 5
Found: 2 5 13
Found: 2 7 11
Found: 3 3 3 3 3 5
Found: 3 3 3 11
Found: 3 3 7 7
Found: 3 5 5 7
Found: 3 17
Found: 5 5 5 5
Found: 7 13
Total: 26
修改上面的程序，去掉分解式的輸出語句，只保留計數功能，分別對N = 100, 200, 300進行測試。結果如下：
-bash-3.2$ time ./a.out
When i = 100:
Total: 40899
real 0m0.114s
user 0m0.112s
sys 0m0.002s
-bash-3.2$ time ./a.out
When i = 200:
Total: 9845164
real 0m38.344s
user 0m38.329s
sys 0m0.001s
-bash-3.2$ time ./a.out
When i = 300:
Total: 627307270
real 50m37.198s
user 50m32.556s
sys 0m1.786s
-bash-3.2$
由結果可見，當N = 300時，分解數就大得嚇人了。
