整数的素数和分解

整数的素数和分解2011-03-29【问题描述】

歌德巴赫猜想说任何一个不小于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 << "
";
    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 << ":
";
    int count = ExpandedGoldbach（i）;
    cout << "Total: " << count << "

";
  }
}