百度笔试题_求自然数因子最小和？
一个自然数可以分解为若干个自然数相乘，对于指定自然数n，请求出每种分解自然数之和最小的一个。
说明：不考虑1，若是素数，则是它本身。
例子：如6=2*3,或是它本身，则2+3最小。
限制：无
要求：完成函数
unsigned int minsum(unsigned int n),n为输入自然数，返回最小的和。
给出思路分析(文字描述)，完成代码，并分析你算法的时间复杂度和空间复杂度。
[解决办法]
分解质因子，全体质因子的和即为最小和。
对 n=a*b*c*... 必定 a + b <= a*b （最小质因子 2）。
[解决办法]
unsigned int minsum(unsigned int n)
{
unsigned int i=2, i2 = 4, sum = 0;
// printf("%d=", n);
while(i2 <= n)
{
if( n%i ==0 )
{
// printf("%d*", i);
n /= i;
sum+=n;
}
else
{
i2 += i++;
i2 += i;
} // i2 = (i+1)*(i+1) = i*i + i + (i+1)
}
// printf("%d\n", n);
return sum+n ;
}
时间复杂度O(n^(1/2)), 空间复杂度O(1)
[解决办法]
该题条件若a*b=n
显然有a+b<n
故该题是算出所有c的因式分解的解，是一些二叉树的森林
而每个因子又是一个二叉树森林
可以递归算法获得其叶子节点
取叶子节点最小的那个就是了
时间复杂度应该是O(n),空间复杂度O(n^(1/2))
[解决办法]
时间负责度 最大为时间复杂度O(n^(1/2)) 当且仅当n^(1/2) 为质数是，实际上按所有整数来算 平均时间复杂度要远小于O(n^(1/2))，比较恰当的时间复杂度应当为a+log(a)n(以a为底的对数) a 为小于O(n^(1/2)) 的最大质数因子
[解决办法]
可以采取折半那种思路找吗?我的想法是这样的
unsigned int minsum(unsigned int n)
{
int temp=n/2;
while(temp!=0){
if(n%temp==0){
if (temp==1&&n/temp==n) return n;
else return minsum(n/temp)+minsum(temp);
}
else temp--;
}
}
