一道算法题.
大于1的正整数n可以分解为：n=x1*x2*...*xm.例如，当n=12时，共有8种不同的分解式：
12 = 12
12 = 6 * 2
12 = 4 * 3
12 = 3 * 4
12 = 3 * 2 * 2
12 = 2 * 6
12 = 2 * 3 * 2
12 = 2 * 2 * 3
要求：对于给定的正整数n，编程计算n共有多少种不同的分解式。
请帮忙指点一下！谢谢！
[解决办法]
1, 进行质分解，计算每个质因子的个数
以12为例，他等于2*2*3，质因子分别是2和3，个数分别是2和1
2. 总的分解方法的种数为各个因子个数＋1的乘积
以12为例，他就是(2+1)*(1+1)=6种
楼主的
12 = 3 * 2 * 2
12 = 2 * 3 * 2
12 = 2 * 2 * 3
如果认为是三种方式的话，就比较麻烦了，还要考虑各种排列
[解决办法]
可以写个递归函数求解
可以循环穷举的算
还可以推导公式
我看过一个推导的
下面以精确计算 1000! 为例，阐述该算法：
记 F1(n) = n*(n-1)*...*1；
F2(n) = n*(n-2)*...*(2 or 1)；
Pow2(r) = 2^r；
有 F1(2k+1) = F2(2k+1) * F2(2k)
= Pow2(k) * F2(2k+1) * F1(k),
F1(2k) = Pow2(k) * F2(2k-1) * F1(k),
及 Pow2(u) * Pow2(v) = Pow2(u+v),
∴ 1000! = F1(1000)
= Pow2(500)*F2(999)*F1(500)
= Pow2(750)*F2(999)*F2(499)*F1(250)
= Pow2(875)*F2(999)*F2(499)*F2(249)*F1(125)
= Pow2(937)*F2(999)*F2(499)*F2(249)*F2(125)*F1(62)
= Pow2(968)*F2(999)*F2(499)*F2(249)*F2(125)*F2(61)*F1(31)
= Pow2(983)*F2(999)*F2(499)*F2(249)*F2(125)*F2(61)*F2(31)*F1(15)
= ...
如果你预存了某些小整数阶乘（比如这里的“F1(15)”），则可提前终止分解，否则直至右边最后一项为“F1(1)”为止；这样，我们将阶乘转化为2的整数次幂与一些连续奇数的积（或再乘以一个小整数的阶乘）；
再定义：F2(e,f) = e*(e-2)*...*(f+2)，这里仍用“F2”，就当是“函数重载”好了:)，
则 F2(e) = F2(e,-1) = F2(e,f)*F2(f,-1) （e、f为奇数，0≤f≤e）
∴ F2(999) = F2(999,499)*F2(499,249)*F2(249,125)*F2(125,61)*F2(61,31)*F2(31),
F2(499) = ____________F2(499,249)*F2(249,125)*F2(125,61)*F2(61,31)*F2(31),
F2(249) = ________________________F2(249,125)*F2(125,61)*F2(61,31)*F2(31),
F2(125) = ____________________________________F2(125,61)*F2(61,31)*F2(31),
F2( 61) = _______________________________________________F2(61,31)*F2(31),
F2( 31) = _________________________________________________________F2(31),
∴ F1(1000) = F1(15) * Pow2(983) * F2(999,499) \
* [F2(499,249)^2] * [F2(249,125)^3] \
* [F2(61,31)^4] * [F2(31)^5]
这样，我们又将阶乘转化为了乘方运算。
上式实际上是个形如 a * b^2 * c^3 * d^4 * e^5 的式子；我们再将指数转化为二进制，可得到如下公式：
a * b^2 * c^3 * d^4 * e^5 = (a*c*e)*[(b*c)^2]*[(d*e)^4]
= (((e*d)^2)*(c*b))^2*(e*c*a)，
即可转化成了可充分利用高效的平方算法
[解决办法]
这不就是自然数拆分吗？
自然数(这里说的自然数不包括0，可能和现在的标准有冲突，下同)拆分是一个经典问题，意思是将一个自然数拆分为多个自然数之和或之积。其基本算法是递归。例如5的拆分，可以化成1+(4的拆分)，2+(3的拆分)。为了保证不重复，我们要求拆分后的序列是不减的，及后项不小于前项。
下面是关于各式折分的算法，你改下就可以变成相积形式了。
/*
自然数拆分
*/
#include <stdio.h>
#include <string.h>
long res[1024],Total;
void fen(long n, long m)//n是需要拆分的数，m是拆分的进度。
{
long rest;
for(long i=1;i<=n;i++)//从1开始尝试拆分。
{
if(i>=res[m-1])//拆分的数大于或等于前一个，保证不重复。(第一个是0，虚拟的，不计入结果)
{
res[m]=i;//将这个数计入结果中。
rest=n-i;//剩下的数是n-i。
if(rest==0&&m>1)//如果已经没有剩下的了，并且进度(总的拆分个数)大于1，说明已经得到一个结果。
{
Total++;
printf("%ld\t",Total);
for(long j=1;j<=m;j++)
{
printf("%ld ",res[j]);
}
printf("\n");
}
else
{
fen(rest,m+1);//否则将剩下的数进行进度为m+1拆分。
}
res[m]=0;//取消本次结果，进行下一次拆分。
}
}
}
int main()
{
long n;
printf("Input n:");
scanf("%ld",&n);
memset(res,0,sizeof(res));
Total=0;
fen(n,1);
return 0;
}
这个程序得到的是所有组合，你从中提取分组数为N的就应该可以了。
