1. 问题描述
一个大于1的正整数可以分解为
。例如，当
时，共有8种不同的分解式：
- 算法设计：对于给定的正整数n，算出共有多少种不同的分解式。
- 数据输入：由文件input.txt给出输入数据。第一行有个正整数
)。
- 结果输入：将计算的不同的分解式的数目输出到文件output.txt中。
1.1. 问题分析
上面描述的分解式不考虑乘法的交换律，所以可以把第一个分解因子看作一个可以被12整除数字的遍历，剩下的因子就是一个递归问题，求解剩下因子的分解式即可，然后把每种因子的分解结果数相加，递归的返回条件是，因子等于1。
int solveInterger(int input){
if(input <= 0){
std::cout<<"input is illegal"<<std::endl;
return -1;
}
int result = 0;
if(input == 1)
return 1;
else
for(int i = input; i > 1 && input % i == 0 ; i--){
result = result + solveInterger(input/i); //每种可整除因子递归结果求和
}
return result;
}
1.2. 算法分析
算法中的循环边界是，其中
是输入的数字，但是能够进入到循环中的次数
肯定小于
。进入循环之后通过递归调用一个更少规模的子问题，输入变成了
。但是这其中必然存在重复多算的过程，即递归的是不独立的子问题，如下面的情形取
：
两种情形的子问题都是求解6的整式分解问题，但是会出现多次求解的冗余过程，当数字n比较小的时候出现的这种情形的可能会比较低，但是当n很大时，会造成很坏的情况。
1.3. 实验验证
result.png
