views:

4753

answers:

4

How do you calculate the least common multiple of multiple numbers?

So far I've only been able to calculate it between two numbers. But have no idea how to expand it to calculate 3 or more numbers.

So far this is how I did it

LCM = num1 * num2 /  gcd ( num1 , num2 )

With gcd is the function to calculate the greatest common divisor for the numbers. Using euclidean algorithm

But I can't figure out how to calculate it for 3 or more numbers.

+19  A: 

You can compute the LCM of more than two numbers by iteratively computing the LCM of two numbers, i.e.

lcm(a,b,c) = lcm(a,lcm(b,c))
A. Rex
thanks. That done it for me
paan
Ooooh textbook recursion :)
Peter Wone
+6  A: 

In Python (modified primes.py):

def gcd(a, b):
    """Return greatest common divisor using Euclid's Algorithm."""
    while b:      
        a, b = b, a % b
    return a

def lcm(a, b):
    """Return lowest common multiple."""
    return a * b // gcd(a, b)

def lcmm(*args):
    """Return lcm of args."""   
    return reduce(lcm, args)

Usage:

>>> lcmm(100, 23, 98)
112700
>>> lcmm(*range(1, 20))
232792560

reduce() works something like that:

def reduce(callable, iterable, ini=None):
    iterable = iter(iterable)

    ret = iterable.next() if ini is None else ini

    for item in iterable:
        ret = callable(ret, item)

    return ret
J.F. Sebastian
I'm not familiar with python, what does reduce() do?
paan
Given a function f and a list l = [a,b,c,d], reduce(f,l) returns f(f(f(a,b),c),d). It's the functional implementation of "lcm can be computed by iteratively computing the lcm of the current value and the next element of the list."
A. Rex
+1  A: 

I just figured this out in Haskell:

lcm' :: Integral a => a -> a -> a
lcm' a b = a`div`(gcd a b) * b
lcm :: Integral a => [a] -> a
lcm (n:ns) = foldr lcm' n ns

I even took the time to write my own gcd function, only to find it in Prelude! Lots of learning for me today :D

Matt Ellen
A: 

Here's an ECMA-style implementation:

function gcd(a, b){
    // Euclidean algorithm
    var t;
    while (b != 0){
        t = b;
        b = a % b;
        a = t;
    }
    return a;
}

function lcm(a, b){
    return (a * b / gcd(a, b));
}

function lcmm(args){
    // Recursively iterate through pairs of arguments
    // i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))

    if(args.length == 2){
        return lcm(args[0], args[1]);
    } else {
        var arg0 = args[0];
        args.shift();
        return lcm(arg0, lcmm(args));
    }
}
Virgil Disgr4ce