DirectX3D 学习

学习DirectX3D

一个自然数可以分解为若干个自然数相乘,求出每种分解自然数之和最少的一个

转  ::
题二:一个自然数可以分解为若干个自然数相乘,求出每种分解自然数之和最少的一个。 如12=2*2*3,和为7=2+2+3
分析:如果把用穷举法把所有可能的组合计算出来,那无疑是复杂的。 假设a=b*c。其中b,c>=2。则a>=2*max{b,c}>=a+b。由此可见a因数分解后的和比a小。显然a的完全因数分解之后的和最小。问题就变成了自然数完全因数分解求和。

#include <math.h>
unsigned 
int minsum(unsigned int n)
{
    unsigned 
int sum = 0;
    unsigned 
int div_idx = 2;
    unsigned 
int sqrt_n=sqrt(n);
    
    
while (1)
    {
        
if (div_idx > sqrt_n)
            break;
        
if (n % div_idx ==0)
        {
            sum 
+= div_idx;
            n 
/= div_idx;
            sqrt_n 
= sqrt(n);
        }
        
else
            div_idx
++;
    }
    return sum
+n;
}

posted on 2008-09-18 14:00 xpcer 阅读(2682) 评论(0)  编辑 收藏 引用 所属分类: C++


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿(1)

随笔分类

随笔档案

Graphics

搜索

最新评论

阅读排行榜

评论排行榜