整数的素数和分解
作者:tyc611.cublog.cn,2008-11-2
【问题描述】
歌德巴赫猜想说任何一个不小于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
#include
#include
#include
using namespace std;
// 计算num内的所有素数(不包括num)
void CalcPrimes(int num, vector &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 &primes, int from, vector &numbers)
{
if (num == 0) {
cout << "Found: ";
copy(numbers.begin(), numbers.end(), ostream_iterator(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 primes;
CalcPrimes(num, primes);
vector 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时,分解数就大得吓人了。
阅读(2399) | 评论(0) | 转发(0) |