optimization - c - 找到多个数字的最小公倍数

程序的目标是找到可以除以数字1到20,而没有任何余数的最小数字。代码工作正常但需要33秒。我能改进让它更快吗?


#include <stdio.h>



int main(){


 int number = 19, i, k;



 label:


 number++;


 k = 0;


 for (i = 1; i <= 20; i++){


 if (number%i == 0){


 k++;


 }


 }



 if (k != 20){


 goto label;


 }



 printf("%dn", number);


 return 0;


}



时间:

更改


int number = 19 ;




int number = 0 ;



然后:

 
number++;



 


number += 20 ;



在onlinegdb.com上,你的算法需要102秒才能运行,而改进后的运行时间不到一秒,并产生了相同的答案。

在注释中建议的素数值的初始乘积将提供进一步的改进。


#include <stdio.h>



/* GCD returns the greatest common divisor of a and b (which must be non-zero).



 This algorithm comes from Euclid, Elements, circa 300 BCE, book (chapter)


 VII, propositions 1 and 2.


*/


static unsigned GCD(unsigned a, unsigned b)


{


 while (0 < b)


 {


 unsigned c = a % b;


 a = b;


 b = c;


 }



 return a;


}



int main(void)


{


 static const unsigned Limit = 20;



 unsigned LCM = 1;



 /* Update LCM to the least common multiple of the LCM so far and the next


 i. The least common multiple is obtained by multiplying the numbers


 and removing the duplicated common factors by dividing by the GCD.


 */


 for (unsigned i = 1; i <= Limit; ++i)


 LCM *= i / GCD(LCM, i);



 printf("The least common multiple of numbers from 1 to %u is %u.n",


 Limit, LCM);


}



...