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

User · Answer

Here is the PHP implementation          https   stackoverflow com q 12412782 1066234     function math gcd  a  b                  a   abs  a             b   abs  b           if  a  lt   b                         list  b  a    array  a  b                      if  b    0                         return  a                           r    a    b          while  r  gt  0                          a    b               b    r               r    a    b                    return  b             function math lcm  a   b                return   a    b   math gcd  a   b                  https   stackoverflow com a 2641293 1066234     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

User · Answer

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

User · Answer

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

User · Answer

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    gt  gt  gt  lcmm 100  23  98  112700  gt  gt  gt  lcmm  range 1  20   232792560   reduce   works something like that    gt  gt  gt  f   lambda a b   f  s  s      a b   gt  gt  gt  print reduce f   abcd   f f f a b  c  d

User · Answer

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  lt  n  i                 res   res a i  gcd res  a i                 return res

User · Answer

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

User · Answer

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

User · Answer

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  gt  1          while  divisor  lt   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   lt  value    if fact not in dict or  lt  val                 high factors key    value     return reduce  MULTIPLY    k    v  for k  v in high factors items

User · Answer

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

User · Answer

Function to find lcm of any list of numbers    def function l        s   1      for i in l          s   lcm i  s       return s

User · Answer

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   amp n     printf  Enter  d  numbers to calculate their LCM    n     for i 0 i lt n i        scanf   d   amp a i     for i 0 i lt 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 gt b            temp a       a b       b temp         if b a  0      return a    else     return gcd two numbers b a a

User · Answer

I just figured this out in Haskell   lcm     Integral a   gt  a - gt  a - gt  a lcm  a b   a div  gcd a b    b lcm    Integral a   gt   a  - gt  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

User · Answer

Here is a C  port of Virgil Disgr4ce s implemenation   public class MathUtils            lt summary gt          Calculates the least common multiple of 2  numbers           lt  summary gt           lt remarks gt          Uses recursion based on lcm a b c    lcm a lcm b c            Ported from http   stackoverflow com a 2641293 420175           lt  remarks gt      public static Int64 LCM IList lt Int64 gt  numbers                if  numbers Count  lt  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 lt Int64 gt  numbers              private static Int64 LCM IList lt Int64 gt  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                    lt summary gt          Finds the greatest common denominator for 2 numbers           lt  summary gt           lt remarks gt          Also from http   stackoverflow com a 2641293 420175           lt  remarks gt      public static Int64 GCD Int64 a  Int64 b                   Euclidean algorithm         Int64 t          while  b    0                        t   b              b   a   b              a   t                    return a

User · Answer

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 lt 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  gt  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

User · Answer

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

User · Answer

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

User · Answer

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  gt  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  lt  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  lt  input length  i              result   lcm result  input i              return result

User · Answer

This is what I used --  def greater n          a num 0         for i in range 0 len n  1          if a lt 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

User · Answer

Here it is in Swift      Euclid s algorithm for finding the greatest common divisor func gcd   a  Int    b  Int  - gt  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  - gt  Int     return m   gcd m  n    n       Returns the least common multiple of multiple numbers  func lcmm   numbers   Int   - gt  Int     return numbers reduce 1    lcm  0   1

User · Answer

In Ruby  it s as simple as    gt   2  3  4  6  reduce  lcm    gt  12   gt   16  32  96  reduce  gcd    gt  16    tested on Ruby 2 2 10 and 2 6 3

User · Answer

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

User · Answer

ES6 style  function gcd    numbers      return numbers reduce  a  b    gt  b     0   a   gcd b  a   b       function lcm    numbers      return numbers reduce  a  b    gt  Math abs a   b    gcd a  b

User · Answer

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

User · Answer

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

User · Answer

GCD needs a little correction for negative numbers   def gcd x y     while y      if y lt 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

User · Answer

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

User · Answer

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       gt  gt  gt  lcm 100 23 98   lcm of  100  23  98  is 112700   gt  gt  gt  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

User · Answer

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

User · Answer

clc   data    1 2 3 4 5   LCM 1   for i 1 1 length data       LCM   lcm LCM data i    end

User · Answer

Method compLCM takes a vector and returns LCM  All the numbers are within vector in numbers   int mathOps  compLCM std  vector lt int gt   amp 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  lt  tmpNumbers  amp  amp  tmpNotDividable    false  i                          if  tmpMax   in numbers i     0                   tmpNotDividable   true                     if  tmpNotDividable    false              return tmpMax          else             tmpMax

User · Answer

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

User · Answer

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

[algorithm] Least common multiple for 3 or more numbers

Examples related to algorithm

Examples related to math

Examples related to lcm