LCM: Least Common Multiplier

[Michael Greenwald]

tif at doorstop.austin.ibm.com (Paul Chamberlain) writes:

>In article <17000004 at uicsl.csl.uiuc.edu> nikki at uicsl.csl.uiuc.edu writes:
>>I am looking for a program which is capable of computing LCM (Least Common
>>Multiplier) of many numbers (Max. of ~20).

(By the way, lcm is a standard part of Common Lisp which might be
available on your machine.  (There are a couple of implementations
that run on most Unix platforms).  I assume, therefore, that you want
it in C).

You can write it pretty simply as follows.  

 #define MAX 64

 /* Not a general purpose gcd - this one expects non-negative integers only,
    and x < y.  Sufficient for lcm, though.
  */
 long gcd(x, y)
      long    x, y;
 {return((x == 0)?y:gcd(y%x, x));}

 /* Assumes that X and all elements of NUMBERS are nonnegative.
    Takes least common multiple of X and the first N integers in the array
    called NUMBERS
  */
 long lcm(x, n, numbers)
      long    x, n, numbers[];
 {
   if ((n > 0) && (x != 0))
     { long   x2;

       x2 = lcm (numbers[--n], n, numbers);
       return ((x2 / ((x<x2)?gcd(x,x2):gcd(x2,x))) * x);
     }
   else return(x);
 }

If you want lcm to take its arguments from the command line and print result
there, then you can add

 void main(argc, argv)
      int    argc;
      char*  argv[];
 {
   int       numbers[MAX], i;

   for (i=1; i<argc; i++)
       sscanf(argv[i],"%ld",&numbers[i-1]);

   printf ("%ld\n", lcm(numbers[argc-2], argc-2, numbers));
 }