c - 找出多个数的最小公倍数

Question

这个程序的目标是找出能被 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("%d\n", number);
  return 0;
}

Answer 1

#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);
}