整数的素数和解析

副标题#e#

【问题描写】

歌德巴赫意料说任何一个不小于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";
　　}
}

#p#副标题#e#

运行功效：

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举办测试。功效如下：

#p#分页标题#e#

-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时，解析数就大得吓人了。