Least common multiple for 3 or more numbers

Question

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.

Answer 1

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))

Answer 2

I would go with this one (C#):

static long LCM(long[] numbers)
{
    return numbers.Aggregate(lcm);
}
static long lcm(long a, long b)
{
    return Math.Abs(a * b) / GCD(a, b);
}
static long GCD(long a, long b)
{
    return b == 0 ? a : GCD(b, a % b);
}

Just some clarifications, because at first glance it doesn't seams so clear what this code is doing:

Aggregate is a Linq Extension method, so you cant forget to add using System.Linq to your references.

Aggregate gets an accumulating function so we can make use of the property lcm(a,b,c) = lcm(a,lcm(b,c)) over an IEnumerable. More on Aggregate

GCD calculation makes use of the Euclidean algorithm.

lcm calculation uses Abs(a*b)/gcd(a,b) , refer to Reduction by the greatest common divisor.

Hope this helps,

Answer 3

Here is a Python one-liner (not counting imports) to return the LCM of the integers from 1 to 20 inclusive:

Python 3.5+ imports:

from functools import reduce
from math import gcd

Python 2.7 imports:

from fractions import gcd

Common logic:

lcm = reduce(lambda x,y: x*y//gcd(x, y), range(1, 21))

In both Python 2 and Python 3, operator precedence rules dictate that the * and // operators have the same precedence, and so they apply from left to right. As such, x*y//z means (x*y)//z and not x*(y//z). The two typically produce different results. This wouldn't have mattered as much for float division but it does for floor division.

Answer 4

clc;

data = [1 2 3 4 5]

LCM=1;

for i=1:1:length(data)

    LCM = lcm(LCM,data(i))

end 

Answer 5

In R, we can use the functions mGCD(x) and mLCM(x) from the package numbers, to compute the greatest common divisor and least common multiple for all numbers in the integer vector x together:

    library(numbers)
    mGCD(c(4, 8, 12, 16, 20))
[1] 4
    mLCM(c(8,9,21))
[1] 504
    # Sequences
    mLCM(1:20)
[1] 232792560

Answer 6

And the Scala version:

def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)
def gcd(nums: Iterable[Int]): Int = nums.reduce(gcd)
def lcm(a: Int, b: Int): Int = if (a == 0 || b == 0) 0 else a * b / gcd(a, b)
def lcm(nums: Iterable[Int]): Int = nums.reduce(lcm)