How to find lcm of multiple numbers using GCD approach?

Question

I'm using the euclidean approach i.e LCM = num1 * num2 / gcd ( num1 , num2 ) I have sucessfully made the code for two numbers but it is buggy if i try it for multiple inputs. my approach can be represented as lcm(a,b,c) = lcm(a,lcm(b,c)) but this approach does not work as they(lcm(a,b,c)and lcm(a,lcm(b,c))) are two different values.

possible duplicate of [Least common multiple for 3 or more numbers](http://stackoverflow.com/questions/147515/least-common-multiple-for-3-or-more-numbers) — Am_I_Helpful, Jul 26 '15 at 20:03
Your approach should work. If it does not, you have a bug in your implementation, in which case you should post your code if you can't figure out what it is. — IVlad, Jul 26 '15 at 20:27
Perhaps your intermediate numbers are overflowing the datatype? — Peter de Rivaz, Jul 26 '15 at 21:03
Have you tried: `LCM = num1 / gcd ( num1 , num2 ) * num2` instead, to avoid overflow? — Juan Lopes, Jul 26 '15 at 21:10

Spektre · Answer 1 · 2015-07-27T17:42:22.737

I compute LCM by Sieves of Eratosthenes like this in C++:

int lcm(int *a,int N,bool _sorted=false)    // least common multiple of a[N]
    {                                       // if sorted a[N] must be: (a0 > a1 > a2 > ... > aN)
    if (N<1) return 0;
    int i,j,c,dc;
    int *b=new int[N];
    if (_sorted) for (i=0;i<N;i++) b[i]=a[i];   // b[N] = a[N]
    else for (c=0x7FFFFFFF,j=0;j<N;j++,c=dc)    // b[N] = insert sort a[N]
        {
        for (dc=0,i=0;i<N;i++)
         if ((dc<a[i])&&(c>a[i])) dc=a[i];
        if (!dc) { N=j; break; }
        b[j]=dc;
        }
    // replace duplicit multiplies with 1
    for (i=  0;i<N;i++) if (b[i]>1)
    for (j=i+1;j<N;j++) if (b[j]>1)
     if (b[i]%b[j]==0) b[j]=1;
    // cut off all ones
    for (j=0,i=0;i<N;i++) if (b[i]>1) { b[j]=b[i]; j++; } N=j;
    if (N<1) return 1;
    // lcm
    for (dc=b[0],i=-1,c=dc;i<0;c+=dc)
     for (i=1;i<N;i++)
      if (c%b[i]!=0) { i=-1; break; }
    c-=dc;
    delete[] b;
    return c;
    }

first ensure that the input numbers are sorted descending (b[] array)
it is an leftover from older code you just need to have the largest num in b[0]
then remove duplicate multiples (for example 8,4,2 ... use only 8)
and at last use the sieve
you do not actually need to store the sieve in memory
instead just compute the sieve incrementally
and remember only the the largest number multiples c
if all the rest of the numbers are divisible you found the result

[edit2] use of gcd

//--------------------------------------------------------------------------
int gcd(int a0,int a1)
    {
    int d,r,r0;
    if (a0<a1) { r=a0; a0=a1; a1=r; }
    // euklid a0/a1
    d=a0/a1;
    r=a0%a1; r0=r;
    if (!r) return a1;
    // a1/r0
    d=a1/r0;
    r=a1%r0;
    if (!r) return r0;
    a0=r0; a1=r;
    for (;;)
        {
        if (a0<a1) { r=a0; a0=a1; a1=r; }
        d=a0/a1;
        r=a0%a1;
        if (!r) return a1;
        a0=a1; a1=r;
        }
    return 0;
    }
//--------------------------------------------------------------------------    
int lcm(int *a,int N)                               // least common multiple of a[N]
        {
        int a0,a1,aa;
        if (N==0) return 0;
        if (N==1) return a[0];
        a0=a[0];
        if (N==2) a1=a[1]; else a1=lcm(a+1,N-1);
        aa=gcd(a0,a1);
        if (N==2) return (a0*a1)/aa;
        return (a1/aa)*a0;
        }
//--------------------------------------------------------------------------

this is much faster then sieves ...

How can this possibly be faster? OP's approach is O(n log W) where n is the number of elements and W is the maximum value. Your is something like O(W log W), which is much worse. Also what's the need for mul/div? You can avoid the overflows much more easily by dividing by the gcd before multiplying and by using 64-bit integers (i.e. `int64_t`). — Niklas B., Jul 27 '15 at 17:20

How to find lcm of multiple numbers using GCD approach?

1 Answers1