现在的位置: 首页 > 综合 > 正文

小于1000000的所有完数算法的优化

2013年08月18日 ⁄ 综合 ⁄ 共 1537字 ⁄ 字号 评论关闭

完数是指其所有因数(不包括其本身)之和等于其本身的数,例如:6 = 1 + 2 + 3,本例是研究求小于1000000的完数的最优算法.编程环境是Dev C++ 4.92

首先,想到的算法如下:

 

int main(int argc, char *argv[])
{
    
int nNum;
    cin
>>nNum;
    time_t tBegin 
= clock();
    
int nSum  = 0;

    
for(int i = 2; i <= nNum; i++)
    
{
     
for(int iFor = 2; iFor <= i / 2; iFor++)
     
{
      
if(i % iFor == 0)
      

              nSum 
+= iFor;                    
      }

     }
  
     
if(nSum == i - 1)
             cout
<<i<<endl;    
     nSum 
= 0;   
    }
 
    time_t tEnd 
= clock();
    printf(
"Time %d ", tEnd - tBegin);
    system(
"PAUSE");
    
return EXIT_SUCCESS;
}

 

运行结果,以小于10000为例子,时间差是1062ms,显然运行效率很低,让我们做点改进,记得求证一个数是不是素数时采用的算法是 i < sqrt(m)的形式,故对原程序做点修改:

 

    for(int i = 2; i <= nNum; i++)
    
{
     
for(int iFor = 2; iFor <= sqrt((float)i); iFor++)
     
{
      
if(i % iFor == 0)
      

              nSum 
+= iFor;              
              nSum 
+= i / iFor;      
      }

     }
  
     
if(nSum == i - 1)
             cout
<<i<<endl;    
     nSum 
= 0;   
    }
 

 

仍是对10000进行测试,结果是30ms,速度提高了一个数量级,但对100000来说,运行时间是2483ms,对1000000来说,运行时间应该在几分钟.

有没有更好的办法?看来只能从sqrt函数入手了,首先他是一个库函数,函数调用有一定的时间损耗,其次,内部是浮点数运算,效率也不高,倘若能解决这个问题,程序的效率会大大提高.因此又做了一部分改进.

     for(int iFor = 2; iFor <= i / iFor; iFor++)

对100000测试的结果是1633ms,又提高了一倍.

乘法的效率比除法要高的多,于是,又改进为

     for(int iFor = 2; iFor * iFor<= i; iFor++)

对100000测试的结果是953ms,又提高近一倍.

              nSum += iFor;             
              nSum += i / iFor;

改进为

              nSum = iFor + i / iFor + nSum;

对100000的测试结果为941,又提高一点.但由于硬件原因,可以不计,最后对1000000测试结果是27740ms

所有的程序都是运行在PIII 1.13下,可能会有一点误差.

总结:在一些对效率要求较严格的时候,特别是重复调用一些函数时,库函数使用时要慎重,自己写的可能会更有效率.

抱歉!评论已关闭.