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.

Irresponsible

please don't tag this as homework. I'm trying to find a way to fit multiple pieces of metal sheets onto a plate and need to find a way to fit different length metal on the same plate. LCM and GCD is the best way to do this. I'ma programmer not a math guy. THat's why I asked. – Irresponsible

Fitting small sheets into a larger sheet -- 2D bin packing ? – Super

@HighPerformanceMark Tetris? – Adjournment

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

Fan

Ooooh textbook recursion :) – Tortious

a recursive algorithm definition does not necessarily mean a recursive subroutine. You can implement this in a loop pretty simply. Thanks for the perfect answer. – Audit

Answer 2

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:

>>> f = lambda a,b: "f(%s,%s)" % (a,b)
>>> print reduce(f, "abcd")
f(f(f(a,b),c),d)

Devito

I'm not familiar with python, what does reduce() do? – Irresponsible

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." – Fan

+1 for showing a solution that can adapt to more than three parameters – Anglo

can you make the lcm function behave like the lcmm function by reducing itself? My first thought is to make it do the lcm() when there are 2 arguments, and do the reduce() when there are more. – Bead

Here's one: enrico-franchi.org/2010/09/nice-functional-lcm-in-python.html – Bead

@endolith: lcmm() is already that function. It works for any len(args) > 0 including len(arg) == 2. – Devito

A minor detail: you can make lcmm work for any number of arguments just adding the identity element to the left fold: reduce(lcm, args, 1). – Cenozoic

You could also use the built-in implementation of gcd instead of your own implementation. – Yahweh

@b4hand: fractions.gcd() is only available since Python 2.6 (the answer has been written before the release) but it doesn't matter because the question has no python tag; therefore the answer should be written to be useful for people who are not familiar with Python i.e., Python is used as an executable pseudo-code here (I understand that using reduce() somewhat contradicts it. I hope the example at the end clarifies what it does). – Devito

I realized the answer was old, but didn't realize that it preceded the release of 2.6 by two days. I still feel the comment is relevant for people who stumble upon this answer now. This shows up highly in Google. Note that I did upvote your answer so don't take the comment as too critical. – Yahweh

I got this working by adding *args instead of args to lcmm function. – Coppola

@A-B-B: you should really read the answer and the comments e.g., this comment. It is the second time today. Obviously, the code works in Python. It works in Python 2—the only version available at the time. – Devito

What do the commas do on line 4? I am not familiar with them as operators and after a brief google search I couldn't find anything. – Somnambulism

@Somnambulism comma creates a tuple in Python. In this case, it is equivalent to: t = a; a = b; b = t % b – Devito

Ahhh, ok, I thought a tuple had to be inside parenthesis. Thanks – Somnambulism

+1 for using reduce; I'd never seen it before now! But I wonder if it isn't deprecated by now? It's been a long time... – Crumb

primes.py already includes def LCM(terms): "Return lcm of a list of numbers." Added to primes.py on Mar 30, 2000. – Solvolysis

Answer 3

Here's an ECMA-style implementation:

function gcd(a, b){
    // Euclidean algorithm
    while (b != 0){
        var temp = b;
        b = a % b;
        a = temp;
    }
    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));
    }
}

Akim

It feels bad that I don't understand what you mean by "ECMA-style" =/ – Lyontine

Answer 4

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,

Indult

Is breaking it down into two-argument LCMs the fastest way? I'm reading this page and there's another algorithm discussed: en.wikipedia.org/wiki/… – Tetrafluoroethylene

Answer 5

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

Uproar

You can use foldr1 for the last line: lcm ns = foldr1 lcm' ns or lcm = foldr1 lcm' – Behnken

You can also dispense with the type signatures, for a really minimal result, as Integral is implied by div – Behnken

Answer 6

Some Python code that doesn't require a function for gcd:

from sys import argv 

def lcm(x,y):
    tmp=x
    while (tmp%y)!=0:
        tmp+=x
    return tmp

def lcmm(*args):
    return reduce(lcm,args)

args=map(int,argv[1:])
print lcmm(*args)

Here's what it looks like in the terminal:

$ python lcm.py 10 15 17
510

Grieve

Answer 7

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

Note that 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.

Schaffel

Answer 8

Here it is in Swift.

// Euclid's algorithm for finding the greatest common divisor
func gcd(_ a: Int, _ b: Int) -> Int {
  let r = a % b
  if r != 0 {
    return gcd(b, r)
  } else {
    return b
  }
}

// Returns the least common multiple of two numbers.
func lcm(_ m: Int, _ n: Int) -> Int {
  return m / gcd(m, n) * n
}

// Returns the least common multiple of multiple numbers.
func lcmm(_ numbers: [Int]) -> Int {
  return numbers.reduce(1) { lcm($0, $1) }
}

Fifine

Answer 9

Here is a C# port of Virgil Disgr4ce's implemenation:

public class MathUtils
{
    /// <summary>
    /// Calculates the least common multiple of 2+ numbers.
    /// </summary>
    /// <remarks>
    /// Uses recursion based on lcm(a,b,c) = lcm(a,lcm(b,c)).
    /// Ported from https://mcmap.net/q/135633/-least-common-multiple-for-3-or-more-numbers.
    /// </remarks>
    public static Int64 LCM(IList<Int64> numbers)
    {
        if (numbers.Count < 2)
            throw new ArgumentException("you must pass two or more numbers");
        return LCM(numbers, 0);
    }

    public static Int64 LCM(params Int64[] numbers)
    {
        return LCM((IList<Int64>)numbers);
    }

    private static Int64 LCM(IList<Int64> numbers, int i)
    {
        // Recursively iterate through pairs of arguments
        // i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))

        if (i + 2 == numbers.Count)
        {
            return LCM(numbers[i], numbers[i+1]);
        }
        else
        {
            return LCM(numbers[i], LCM(numbers, i+1));
        }
    }

    public static Int64 LCM(Int64 a, Int64 b)
    {
        return (a * b / GCD(a, b));
    }

    /// <summary>
    /// Finds the greatest common denominator for 2 numbers.
    /// </summary>
    /// <remarks>
    /// Also from https://mcmap.net/q/135633/-least-common-multiple-for-3-or-more-numbers.
    /// </remarks>
    public static Int64 GCD(Int64 a, Int64 b)
    {
        // Euclidean algorithm
        Int64 t;
        while (b != 0)
        {
            t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
}'

Devitt

Answer 10

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)

Berwickupontweed

Corrected lcm implementation def lcm(nums: Iterable[Int]): Int = nums.reduceRight(lcm) – Lindley

Answer 11

Function to find lcm of any list of numbers:

 def function(l):
     s = 1
     for i in l:
        s = lcm(i, s)
     return s

Cavetto

Answer 12

Using LINQ you could write:

static int LCM(int[] numbers)
{
    return numbers.Aggregate(LCM);
}

static int LCM(int a, int b)
{
    return a * b / GCD(a, b);
}

Should add using System.Linq; and don't forget to handle the exceptions ...

Lister

Answer 13

Just for fun, a shell (almost any shell) implementation:

#!/bin/sh
gcd() {   # Calculate $1 % $2 until $2 becomes zero.
      until [ "$2" -eq 0 ]; do set -- "$2" "$(($1%$2))"; done
      echo "$1"
      }

lcm() {   echo "$(( $1 / $(gcd "$1" "$2") * $2 ))";   }

while [ $# -gt 1 ]; do
    t="$(lcm "$1" "$2")"
    shift 2
    set -- "$t" "$@"
done
echo "$1"

try it with:

$ ./script 2 3 4 5 6

to get

60

The biggest input and result should be less than (2^63)-1 or the shell math will wrap.

Puiia

Answer 14

Here is the PHP implementation:

    // https://mcmap.net/q/137473/-simplify-a-fraction/1066234
    function math_gcd($a,$b) 
    {
        $a = abs($a); 
        $b = abs($b);
        if($a < $b) 
        {
            list($b,$a) = array($a,$b); 
        }
        if($b == 0) 
        {
            return $a;      
        }
        $r = $a % $b;
        while($r > 0) 
        {
            $a = $b;
            $b = $r;
            $r = $a % $b;
        }
        return $b;
    }

    function math_lcm($a, $b)
    {
        return ($a * $b / math_gcd($a, $b));
    }

    // https://mcmap.net/q/135633/-least-common-multiple-for-3-or-more-numbers
    function math_lcmm($args)
    {
        // Recursively iterate through pairs of arguments
        // i.e. lcm(args[0], lcm(args[1], lcm(args[2], args[3])))

        if(count($args) == 2)
        {
            return math_lcm($args[0], $args[1]);
        }
        else 
        {
            $arg0 = $args[0];
            array_shift($args);
            return math_lcm($arg0, math_lcmm($args));
        }
    }

    // fraction bonus
    function math_fraction_simplify($num, $den) 
    {
        $g = math_gcd($num, $den);
        return array($num/$g, $den/$g);
    }


    var_dump( math_lcmm( array(4, 7) ) ); // 28
    var_dump( math_lcmm( array(5, 25) ) ); // 25
    var_dump( math_lcmm( array(3, 4, 12, 36) ) ); // 36
    var_dump( math_lcmm( array(3, 4, 7, 12, 36) ) ); // 252

Credits go to @T3db0t with his answer above (ECMA-style code).

Ebony

Answer 15

you can do it another way - Let there be n numbers.Take a pair of consecutive numbers and save its lcm in another array. Doing this at first iteration program does n/2 iterations.Then next pick up pair starting from 0 like (0,1) , (2,3) and so on.Compute their LCM and store in another array. Do this until you are left with one array. (it is not possible to find lcm if n is odd)

Demonstrator

Answer 16

ES6 style

function gcd(...numbers) {
  return numbers.reduce((a, b) => b === 0 ? a : gcd(b, a % b));
}

function lcm(...numbers) {
  return numbers.reduce((a, b) => Math.abs(a * b) / gcd(a, b));
}

Juxtaposition

You called gcd(a, b) but the gdc function expects an array so you meant to call gcd([a, b]) – Unwilled

this is the most elegant answer by far – Deliladelilah

Answer 17

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

Befriend

Answer 18

i was looking for gcd and lcm of array elements and found a good solution in the following link.

https://www.hackerrank.com/challenges/between-two-sets/forum

which includes following code. The algorithm for gcd uses The Euclidean Algorithm explained well in the link below.

https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/the-euclidean-algorithm

private static int gcd(int a, int b) {
    while (b > 0) {
        int temp = b;
        b = a % b; // % is remainder
        a = temp;
    }
    return a;
}

private static int gcd(int[] input) {
    int result = input[0];
    for (int i = 1; i < input.length; i++) {
        result = gcd(result, input[i]);
    }
    return result;
}

private static int lcm(int a, int b) {
    return a * (b / gcd(a, b));
}

private static int lcm(int[] input) {
    int result = input[0];
    for (int i = 1; i < input.length; i++) {
        result = lcm(result, input[i]);
    }
    return result;
}

Lionfish

Answer 19

GCD needs a little correction for negative numbers:

def gcd(x,y):
  while y:
    if y<0:
      x,y=-x,-y
    x,y=y,x % y
    return x

def gcdl(*list):
  return reduce(gcd, *list)

def lcm(x,y):
  return x*y / gcd(x,y)

def lcml(*list):
  return reduce(lcm, *list)

Lawana

Answer 20

How about this?

from operator import mul as MULTIPLY

def factors(n):
    f = {} # a dict is necessary to create 'factor : exponent' pairs 
    divisor = 2
    while n > 1:
        while (divisor <= n):
            if n % divisor == 0:
                n /= divisor
                f[divisor] = f.get(divisor, 0) + 1
            else:
                divisor += 1
    return f


def mcm(numbers):
    #numbers is a list of numbers so not restricted to two items
    high_factors = {}
    for n in numbers:
        fn = factors(n)
        for (key, value) in fn.iteritems():
            if high_factors.get(key, 0) < value: # if fact not in dict or < val
                high_factors[key] = value
    return reduce (MULTIPLY, ((k ** v) for k, v in high_factors.items()))

Adulteration

Answer 21

clc;

data = [1 2 3 4 5]

LCM=1;

for i=1:1:length(data)

    LCM = lcm(LCM,data(i))

end 

Kleist

Code is appreciated, but if you can add comments detailing how it works it's appreciated even more. – Diastasis

While this code snippet may solve the question, including an explanation really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, not just the person asking now! Please edit your answer to add explanation, and give an indication of what limitations and assumptions apply. – Palladous

Answer 22

We have working implementation of Least Common Multiple on Calculla which works for any number of inputs also displaying the steps.

What we do is:

0: Assume we got inputs[] array, filled with integers. So, for example:
   inputsArray = [6, 15, 25, ...]
   lcm = 1

1: Find minimal prime factor for each input.
   Minimal means for 6 it's 2, for 25 it's 5, for 34 it's 17
   minFactorsArray = []

2: Find lowest from minFactors:
   minFactor = MIN(minFactorsArray)

3: lcm *= minFactor

4: Iterate minFactorsArray and if the factor for given input equals minFactor, then divide the input by it:
  for (inIdx in minFactorsArray)
    if minFactorsArray[inIdx] == minFactor
      inputsArray[inIdx] \= minFactor

5: repeat steps 1-4 until there is nothing to factorize anymore. 
   So, until inputsArray contains only 1-s.

And that's it - you got your lcm.

Jandel

Answer 23

LCM is both associative and commutative.

LCM(a,b,c)=LCM(LCM(a,b),c)=LCM(a,LCM(b,c))

here is sample code in C:

int main()
{
  int a[20],i,n,result=1;  // assumption: count can't exceed 20
  printf("Enter number of numbers to calculate LCM(less than 20):");
  scanf("%d",&n);
  printf("Enter %d  numbers to calculate their LCM :",n);
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
 for(i=0;i<n;i++)
   result=lcm(result,a[i]);
 printf("LCM of given numbers = %d\n",result);
 return 0;
}

int lcm(int a,int b)
{
  int gcd=gcd_two_numbers(a,b);
  return (a*b)/gcd;
}

int gcd_two_numbers(int a,int b)
{
   int temp;
   if(a>b)
   {
     temp=a;
     a=b;
     b=temp;
   }
  if(b%a==0)
    return a;
  else
    return gcd_two_numbers(b%a,a);
}

Carbo

Answer 24

Method compLCM takes a vector and returns LCM. All the numbers are within vector in_numbers.

int mathOps::compLCM(std::vector<int> &in_numbers)
 {
    int tmpNumbers = in_numbers.size();
    int tmpMax = *max_element(in_numbers.begin(), in_numbers.end());
    bool tmpNotDividable = false;

    while (true)
    {
        for (int i = 0; i < tmpNumbers && tmpNotDividable == false; i++)
        {
            if (tmpMax % in_numbers[i] != 0 )
                tmpNotDividable = true;
        }

        if (tmpNotDividable == false)
            return tmpMax;
        else
            tmpMax++;
    }
}

Zoellick

Answer 25

For anyone looking for quick working code, try this:

I wrote a function lcm_n(args, num) which computes and returns the lcm of all the numbers in the array args. The second parameternum is the count of numbers in the array.

Put all those numbers in an array args and then call the function like lcm_n(args,num);

This function returns the lcm of all those numbers.

Here is the implementation of the function lcm_n(args, num):

int lcm_n(int args[], int num) //lcm of more than 2 numbers
{
    int i, temp[num-1];

    if(num==2)
    {
        return lcm(args[0], args[1]);
    }
    else
    {
        for(i=0;i<num-1;i++)
        {
           temp[i] = args[i];   
        }

        temp[num-2] = lcm(args[num-2], args[num-1]);
        return lcm_n(temp,num-1);
    }
}

This function needs below two functions to work. So, just add them along with it.

int lcm(int a, int b) //lcm of 2 numbers
{
    return (a*b)/gcd(a,b);
}


int gcd(int a, int b) //gcd of 2 numbers
{
    int numerator, denominator, remainder;

    //Euclid's algorithm for computing GCD of two numbers
    if(a > b)
    {
        numerator = a;
        denominator = b;
    }
    else
    {
        numerator = b;
        denominator = a;
    }
    remainder = numerator % denominator;

    while(remainder != 0)
    {
        numerator   = denominator;
        denominator = remainder;
        remainder   = numerator % denominator;
    }

    return denominator;
}

Zinnia

Answer 26

int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a%b); } int lcm(int[] a, int n) { int res = 1, i; for (i = 0; i < n; i++) { res = res*a[i]/gcd(res, a[i]); } return res; }

Editorialize

Answer 27

In python:

def lcm(*args):
    """Calculates lcm of args"""
    biggest = max(args) #find the largest of numbers
    rest = [n for n in args if n != biggest] #the list of the numbers without the largest
    factor = 1 #to multiply with the biggest as long as the result is not divisble by all of the numbers in the rest
    while True:
        #check if biggest is divisble by all in the rest:
        ans = False in [(biggest * factor) % n == 0 for n in rest]
        #if so the clm is found break the loop and return it, otherwise increment factor by 1 and try again
        if not ans:
            break
        factor += 1
    biggest *= factor
    return "lcm of {0} is {1}".format(args, biggest)

---

>>> lcm(100,23,98)
'lcm of (100, 23, 98) is 112700'
>>> lcm(*range(1, 20))
'lcm of (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19) is 232792560'

Superfluity

Answer 28

This is what I used --

def greater(n):

      a=num[0]

      for i in range(0,len(n),1):
       if(a<n[i]):
        a=n[i]
      return a

r=input('enter limit')

num=[]

for x in range (0,r,1):

    a=input('enter number ')
    num.append(a)
a= greater(num)

i=0

while True:

    while (a%num[i]==0):
        i=i+1
        if(i==len(num)):
               break
    if i==len(num):
        print 'L.C.M = ',a
        break
    else:
        a=a+1
        i=0

Minuend

Answer 29

for python 3:

from functools import reduce

gcd = lambda a,b: a if b==0 else gcd(b, a%b)
def lcm(lst):        
    return reduce(lambda x,y: x*y//gcd(x, y), lst)  

Indult

Answer 30

In Ruby, it's as simple as:

> [2, 3, 4, 6].reduce(:lcm)
=> 12

> [16, 32, 96].reduce(:gcd)
=> 16

(tested on Ruby 2.2.10 and 2.6.3.)

Incumber

Answer 31

Python 3.9 math module's gcd and lcm support over a list of numbers.

import math

lst = [1,2,3,4,5,6,7,8,9]

print(math.lcm(*lst))

print(math.gcd(*lst))

Oliphant

Answer 32

If there's no time-constraint, this is fairly simple and straight-forward:

def lcm(a,b,c):
    for i in range(max(a,b,c), (a*b*c)+1, max(a,b,c)):
        if i%a == 0 and i%b == 0 and i%c == 0:
            return i

Golgi

Can you argue how a number smaller than the maximum of a set of numbers can be an integral multiple of each of them? – Sweeting

@Sweeting you're right, I changed it to maximum of the set of numbers. And it checks in increments of the maximum number. – Golgi

That's an improvement. If you continue that line of thinking, you will discover more. – Sweeting