Least common multiple

Compute the least common multiple of two integers.

Given m and n, the least common multiple is the smallest positive integer that has both m and n as factors. For example, the least common multiple of 12 and 18 is 36, because 12 is a factor (12 × 3 = 36), and 18 is a factor (18 × 2 = 36), and there is no positive integer less than 36 that has both factors. As a special case, if either m or n is zero, then the least common multiple is zero.

One way to calculate the least common multiple is to iterate all the multiples of m, until you find one that is also a multiple of n.

If you already have gcd for greatest common divisor, then this formula calculates lcm.

$\operatorname {lcm} (m,n)={\frac {|m\times n|}{\operatorname {gcd} (m,n)}}$

One can also find lcm by merging the prime decompositions of both m and n.

References: MathWorld, Wikipedia.

Ada

lcm_test.adb: <lang Ada>with Ada.Text_IO; use Ada.Text_IO;

procedure Lcm_Test is

  function Gcd (A, B : Integer) return Integer is
     M : Integer := A;
     N : Integer := B;
     T : Integer;
  begin
     while N /= 0 loop
        T := M;
        M := N;
        N := T mod N;
     end loop;
     return M;
  end Gcd;

  function Lcm (A, B : Integer) return Integer is
  begin
     if A = 0 or B = 0 then
        return 0;
     end if;
     return abs (A) * (abs (B) / Gcd (A, B));
  end Lcm;

begin

  Put_Line ("LCM of 12, 18 is" & Integer'Image (Lcm (12, 18)));
  Put_Line ("LCM of -6, 14 is" & Integer'Image (Lcm (-6, 14)));
  Put_Line ("LCM of 35, 0 is" & Integer'Image (Lcm (35, 0)));

end Lcm_Test;</lang>

Output:

LCM of 12, 18 is 36
LCM of -6, 14 is 42
LCM of 35, 0 is 0

AutoHotkey

<lang autohotkey>LCM(Number1,Number2) {

If (Number1 = 0 || Number2 = 0)
 Return
Var := Number1 * Number2
While, Number2
 Num := Number2, Number2 := Mod(Number1,Number2), Number1 := Num
Return, Var // Number1

}

Num1 = 12 Num2 = 18 MsgBox % LCM(Num1,Num2)</lang>

AutoIt

<lang AutoIt> Func _LCM($a, $b) Local $c, $f, $m = $a, $n = $b $c = 1 While $c <> 0 $f = Int($a / $b) $c = $a - $b * $f If $c <> 0 Then $a = $b $b = $c EndIf WEnd Return $m * $n / $b EndFunc ;==>_LCM </lang> Example <lang AutoIt> ConsoleWrite(_LCM(12,18) & @LF) ConsoleWrite(_LCM(-5,12) & @LF) ConsoleWrite(_LCM(13,0) & @LF) </lang>

36
60
0

--BugFix (talk) 14:32, 15 November 2013 (UTC)

AWK

<lang awk># greatest common divisor function gcd(m, n, t) { # Euclid's method while (n != 0) { t = m m = n n = t % n } return m }

least common multiple

function lcm(m, n, r) { if (m == 0 || n == 0) return 0 r = m * n / gcd(m, n) return r < 0 ? -r : r }

Read two integers from each line of input.
Print their least common multiple.

{ print lcm($1, $2) }</lang>

Example input and output:

$ awk -f lcd.awk
12 18
36
-6 14
42
35 0
0

BBC BASIC

Works with: BBC BASIC for Windows

     DEF FN_LCM(M%,N%)
     IF M%=0 OR N%=0 THEN =0 ELSE =ABS(M%*N%)/FN_GCD_Iterative_Euclid(M%, N%)
     
     DEF FN_GCD_Iterative_Euclid(A%, B%)
     LOCAL C%
     WHILE B%
       C% = A%
       A% = B%
       B% = C% MOD B%
     ENDWHILE
     = ABS(A%)

</lang>

bc

Translation of: AWK

<lang bc>/* greatest common divisor */ define g(m, n) { auto t

/* Euclid's method */ while (n != 0) { t = m m = n n = t % n } return (m) }

/* least common multiple */ define l(m, n) { auto r

if (m == 0 || n == 0) return (0) r = m * n / g(m, n) if (r < 0) return (-r) return (r) }</lang>

Bracmat

We utilize the fact that Bracmat simplifies fractions (using Euclid's algorithm). The function den$number returns the denominator of a number. <lang bracmat>(gcd=

a b

. !arg:(?a.?b)

 &   den$(!a*!b^-1)
   * (!a:<0&-1|1)
   * !a

); out$(gcd$(12.18) gcd$(-6.14) gcd$(35.0) gcd$(117.18))</lang> Output:

36 42 35 234

C

<lang C>#include <stdio.h>

int gcd(int m, int n) {

       int tmp;
       while(m) { tmp = m; m = n % m; n = tmp; }       
       return n;

}

int lcm(int m, int n) {

       return m / gcd(m, n) * n;

}

int main() {

       printf("lcm(35, 21) = %d\n", lcm(21,35));
       return 0;

}</lang>

C++

Library: Boost

<lang cpp>#include <boost/math/common_factor.hpp>

include <iostream>

int main( ) {

  std::cout << "The least common multiple of 12 and 18 is " << 
     boost::math::lcm( 12 , 18 ) << " ,\n"
     << "and the greatest common divisor " << boost::math::gcd( 12 , 18 ) << " !" << std::endl ;
  return 0 ;

}</lang>

Output:

The least common multiple of 12 and 18 is 36 ,
and the greatest common divisor 6 !

C#

<lang csharp>public static int Lcm(int m, int n)

   {
     int r = 0;
     Func<int, int, int> gcd = delegate(int m2, int n2)
                                 {
                                   while (n2!=0)
                                   {
                                     var t2 = m2;
                                     m2 = n2;
                                     n2 = t2%n2;
                                   }
                                   return m2;
                                 };
     
     try
     {
       if (m == 0 || n == 0)
         throw new ArgumentException();
       r = Math.Abs(m*n)/gcd(m, n);
     }
     catch(Exception exception)
     {
       Console.WriteLine(exception.Message);
     }
     return (r<0) ? -r : r;
   }</lang>

Clojure

<lang Clojure>(defn gcd

     [a b]
     (if (zero? b)
     a
     (recur b, (mod a b))))

(defn lcm

     [a b]
     (/ (* a b) (gcd a b)))</lang>

COBOL

<lang cobol> IDENTIFICATION DIVISION.

      PROGRAM-ID. show-lcm.

      ENVIRONMENT DIVISION.
      CONFIGURATION SECTION.
      REPOSITORY.
          FUNCTION lcm
          .
      PROCEDURE DIVISION.
          DISPLAY "lcm(35, 21) = " FUNCTION lcm(35, 21)
          GOBACK
          .
      END PROGRAM show-lcm.

      IDENTIFICATION DIVISION.
      FUNCTION-ID. lcm.
      
      ENVIRONMENT DIVISION.
      CONFIGURATION SECTION.
      REPOSITORY.
          FUNCTION gcd
          .
      DATA DIVISION.
      LINKAGE SECTION.
      01  m                       PIC S9(8).
      01  n                       PIC S9(8).
      01  ret                     PIC S9(8).

      PROCEDURE DIVISION USING VALUE m, n RETURNING ret.
          COMPUTE ret = FUNCTION ABS(m * n) / FUNCTION gcd(m, n)
          GOBACK
          .
      END FUNCTION lcm.
          
      IDENTIFICATION DIVISION.
      FUNCTION-ID. gcd.

      DATA DIVISION.
      LOCAL-STORAGE SECTION.
      01  temp                    PIC S9(8).

      01  x                       PIC S9(8).
      01  y                       PIC S9(8).

      LINKAGE SECTION.
      01  m                       PIC S9(8).
      01  n                       PIC S9(8).
      01  ret                     PIC S9(8).

      PROCEDURE DIVISION USING VALUE m, n RETURNING ret.
          MOVE m to x
          MOVE n to y

          PERFORM UNTIL y = 0
              MOVE x TO temp
              MOVE y TO x
              MOVE FUNCTION MOD(temp, y) TO Y
          END-PERFORM

          MOVE FUNCTION ABS(x) TO ret
          GOBACK
          .
      END FUNCTION gcd.</lang>

Common Lisp

Common Lisp provides the lcm function. It can accept two or more (or less) parameters.

Here is one way to reimplement it.

<lang lisp>CL-USER> (defun my-lcm (&rest args) (reduce (lambda (m n) (cond ((or (= m 0) (= n 0)) 0) (t (abs (/ (* m n) (gcd m n)))))) args :initial-value 1)) MY-LCM CL-USER> (my-lcm 12 18) 36 CL-USER> (my-lcm 12 18 22) 396</lang>

In this code, the lambda finds the least common multiple of two integers, and the reduce transforms it to accept any number of parameters. The reduce operation exploits how lcm is associative, (lcm a b c) == (lcm (lcm a b) c); and how 1 is an identity, (lcm 1 a) == a.

D

<lang d>import std.stdio, std.bigint, std.math;

T gcd(T)(T a, T b) pure /*nothrow*/ {

   while (b) {
       immutable t = b;
       b = a % b;
       a = t;
   }
   return a;

}

T lcm(T)(T m, T n) pure /*nothrow*/ {

   if (m == 0) return m;
   if (n == 0) return n;
   return abs((m * n) / gcd(m, n));

}

void main() {

   lcm(12, 18).writeln;
   lcm("2562047788015215500854906332309589561".BigInt,
       "6795454494268282920431565661684282819".BigInt).writeln;

}</lang>

Output:

36
15669251240038298262232125175172002594731206081193527869

DWScript

<lang delphi>PrintLn(Lcm(12, 18));</lang> Output:

Erlang

<lang erlang>% Implemented by Arjun Sunel -module(lcm). -export([main/0]).

main() -> lcm(-3,4).

gcd(A, 0) -> A;

gcd(A, B) -> gcd(B, A rem B).

lcm(A,B) -> abs(A*B div gcd(A,B)).</lang>

Output:

Euphoria

<lang euphoria>function gcd(integer m, integer n)

   integer tmp
   while m do
       tmp = m
       m = remainder(n,m)
       n = tmp
   end while
   return n

end function

function lcm(integer m, integer n)

   return m / gcd(m, n) * n

end function</lang>

Excel

Excel's LCM can handle multiple values. type in a cell:

This will get the LCM on the first 10 cells in the first row. Thus :

<lang> 12 3 5 23 13 67 15 9 4 2

3605940 </lang>

Ezhil

1. இந்த நிரல் இரு எண்களுக்கு இடையிலான மீச்சிறு பொது மடங்கு (LCM), மீப்பெரு பொது வகுத்தி (GCD) என்ன என்று கணக்கிடும்

நிரல்பாகம் மீபொம(எண்1, எண்2)

@(எண்1 == எண்2) ஆனால்

 ## இரு எண்களும் சமம் என்பதால், மீபொம அந்த எண்ணேதான்

பின்கொடு எண்1

@(எண்1 > எண்2) இல்லைஆனால்

சிறியது = எண்2 பெரியது = எண்1

இல்லை

சிறியது = எண்1 பெரியது = எண்2

முடி

மீதம் = பெரியது % சிறியது

@(மீதம் == 0) ஆனால்

 ## பெரிய எண்ணில் சிறிய எண் மீதமின்றி வகுபடுவதால், பெரிய எண்தான் மீபொம

பின்கொடு பெரியது

இல்லை

தொடக்கம் = பெரியது + 1 நிறைவு = சிறியது * பெரியது

@(எண் = தொடக்கம், எண் <= நிறைவு, எண் = எண் + 1) ஆக

   ## ஒவ்வோர் எண்ணாக எடுத்துக்கொண்டு தரப்பட்ட இரு எண்களாலும் வகுத்துப் பார்க்கின்றோம். முதலாவதாக இரண்டாலும் மீதமின்றி வகுபடும் எண்தான் மீபொம

மீதம்1 = எண் % சிறியது மீதம்2 = எண் % பெரியது

@((மீதம்1 == 0) && (மீதம்2 == 0)) ஆனால் பின்கொடு எண் முடி

முடி

அ = int(உள்ளீடு("ஓர் எண்ணைத் தாருங்கள் ")) ஆ = int(உள்ளீடு("இன்னோர் எண்ணைத் தாருங்கள் "))

பதிப்பி "நீங்கள் தந்த இரு எண்களின் மீபொம (மீச்சிறு பொது மடங்கு, LCM) = ", மீபொம(அ, ஆ) </lang>

F#

<lang fsharp>let rec gcd x y = if y = 0 then abs x else gcd y (x % y)

let lcm x y = x * y / (gcd x y)</lang>

Factor

The vocabulary math.functions already provides lcm.

<lang factor>USING: math.functions prettyprint ; 26 28 lcm .</lang>

This program outputs 364.

One can also reimplement lcm.

<lang factor>USING: kernel math prettyprint ; IN: script

gcd ( a b -- c )

   [ abs ] [
       [ nip ] [ mod ] 2bi gcd
   ] if-zero ;

lcm ( a b -- c )

   [ * abs ] [ gcd ] 2bi / ;

26 28 lcm .</lang>

Forth

<lang forth>: gcd ( a b -- n )

 begin dup while tuck mod repeat drop ;

lcm ( a b -- n )

 over 0= over 0= or if 2drop 0 exit then
 2dup gcd abs */ ;</lang>

Frink

Frink has a built-in LCM function that handles arbitrarily-large integers. <lang frink> println[lcm[2562047788015215500854906332309589561, 6795454494268282920431565661684282819]] </lang>

GAP

<lang gap># Built-in LcmInt(12, 18);

36</lang>

Go

<lang go>package main

import (

   "fmt"
   "math/big"

)

var m, n, z big.Int

func init() {

   m.SetString("2562047788015215500854906332309589561", 10)
   n.SetString("6795454494268282920431565661684282819", 10)

}

func main() {

   fmt.Println(z.Mul(z.Div(&m, z.GCD(nil, nil, &m, &n)), &n))

}</lang>

Output:

15669251240038298262232125175172002594731206081193527869

Haskell

That is already available as the function lcm in the Prelude. Here's the implementation:

<lang haskell>lcm :: (Integral a) => a -> a -> a lcm _ 0 = 0 lcm 0 _ = 0 lcm x y = abs ((x `quot` (gcd x y)) * y)</lang>

Icon and Unicon

The lcm routine from the Icon Programming Library uses gcd. The routine is

<lang Icon>link numbers procedure main() write("lcm of 18, 36 = ",lcm(18,36)) write("lcm of 0, 9 36 = ",lcm(0,9)) end</lang>

Library: Icon Programming Library

numbers provides lcm and gcd and looks like this: <lang Icon>procedure lcm(i, j) #: least common multiple

  if (i =  0) | (j = 0) then return 0	
  return abs(i * j) / gcd(i, j)

end</lang>

J

J provides the dyadic verb *. which returns the least common multiple of its left and right arguments.

<lang j> 12 *. 18 36

  12 *. 18 22

36 132

  *./ 12 18 22

396

  0 1 0 1 *. 0 0 1 1  NB. for boolean arguments (0 and 1) it is equivalent to "and"

0 0 0 1

  *./~ 0 1

0 0 0 1</lang>

Java

<lang java>import java.util.Scanner;

public class LCM{

  public static void main(String[] args){
     Scanner aScanner = new Scanner(System.in);
  
     //prompts user for values to find the LCM for, then saves them to m and n
     System.out.print("Enter the value of m:");
     int m = aScanner.nextInt();
     System.out.print("Enter the value of n:");
     int n = aScanner.nextInt();
     int lcm = (n == m || n == 1) ? m :(m == 1 ? n : 0);
     /* this section increases the value of mm until it is greater  
     / than or equal to nn, then does it again when the lesser 
     / becomes the greater--if they aren't equal. If either value is 1,
     / no need to calculate*/
     if (lcm == 0) {
        int mm = m, nn = n;
        while (mm != nn) {
            while (mm < nn) { mm += m; }
            while (nn < mm) { nn += n; }
        }  
        lcm = mm;
     }
     System.out.println("lcm(" + m + ", " + n + ") = " + lcm);
  }

}</lang>

Julia

Built-in function: <lang julia>lcm(m,n)</lang>

K

<lang K> gcd:{:[~x;y;_f[y;x!y]]}

  lcm:{_abs _ x*y%gcd[x;y]}

  lcm .'(12 18; -6 14; 35 0)

36 42 0

  lcm/1+!20

232792560</lang>

LabVIEW

Requires GCD. This image is a VI Snippet, an executable image of LabVIEW code. The LabVIEW version is shown on the top-right hand corner. You can download it, then drag-and-drop it onto the LabVIEW block diagram from a file browser, and it will appear as runnable, editable code.

Lasso

<lang Lasso>define gcd(a,b) => { while(#b != 0) => { local(t = #b) #b = #a % #b #a = #t } return #a } define lcm(m,n) => { #m == 0 || #n == 0 ? return 0 local(r = (#m * #n) / decimal(gcd(#m, #n))) return integer(#r)->abs }

lcm(-6, 14) lcm(2, 0) lcm(12, 18) lcm(12, 22) lcm(7, 31)</lang>

Output:

Liberty BASIC

<lang lb>print "Least Common Multiple of 12 and 18 is ";LCM(12,18) end

function LCM(m,n)

   LCM=abs(m*n)/GCD(m,n)
   end function

function GCD(a,b)

   while b
       c = a
       a = b
       b = c mod b
   wend
   GCD = abs(a)
   end function
</lang>

Logo

<lang logo>to abs :n

 output sqrt product :n :n

end

to gcd :m :n

 output ifelse :n = 0 [ :m ] [ gcd :n modulo :m :n ]

end

to lcm :m :n

 output quotient (abs product :m :n) gcd :m :n

end</lang>

Demo code:

<lang logo>print lcm 38 46</lang>

Output:

Lua

<lang lua>function gcd( m, n )

   while n ~= 0 do
       local q = m
       m = n
       n = q % n
   end
   return m

end

function lcm( m, n )

   return ( m ~= 0 and n ~= 0 ) and m * n / gcd( m, n ) or 0

end

print( lcm(12,18) )</lang>

Maple

The least common multiple of two integers is computed by the built-in procedure ilcm in Maple. This should not be confused with lcm, which computes the least common multiple of polynomials. <lang Maple>> ilcm( 12, 18 );

</lang>

Mathematica

MATLAB / Octave

Maxima

<lang maxima>lcm(a, b); /* a and b may be integers or polynomials */

/* In Maxima the gcd of two integers is always positive, and a * b = gcd(a, b) * lcm(a, b), so the lcm may be negative. To get a positive lcm, simply do */

abs(lcm(a, b))</lang>

МК-61/52

Objeck

Translation of: C

<lang objeck> class LCM {

 function : Main(args : String[]) ~ Nil {
   IO.Console->Print("lcm(35, 21) = ")->PrintLine(lcm(21,35));
 }
 
 function : lcm(m : Int, n : Int) ~ Int {
   return m / gcd(m, n) * n;
 }
 
 function : gcd(m : Int, n : Int) ~ Int {
   tmp : Int;
   while(m <> 0) { tmp := m; m := n % m; n := tmp; };
   return n;
 }

} </lang>

OCaml

<lang ocaml>let rec gcd u v =

 if v <> 0 then (gcd v (u mod v))
 else (abs u)

let lcm m n =

 match m, n with
 | 0, _ | _, 0 -> 0
 | m, n -> abs (m * n) / (gcd m n)

let () =

 Printf.printf "lcm(35, 21) = %d\n" (lcm 21 35)</lang>

ooRexx

<lang ooRexx> say lcm(18, 12)

-- calculate the greatest common denominator of a numerator/denominator pair

routine gcd private

 use arg x, y

 loop while y \= 0
     -- check if they divide evenly
     temp = x // y
     x = y
     y = temp
 end
 return x

-- calculate the least common multiple of a numerator/denominator pair

routine lcm private

 use arg x, y
 return x / gcd(x, y) * y

</lang>

Order

Translation of: bc

<lang c>#include <order/interpreter.h>

define ORDER_PP_DEF_8gcd ORDER_PP_FN( \

8fn(8U, 8V, \

   8if(8isnt_0(8V), 8gcd(8V, 8remainder(8U, 8V)), 8U)))

define ORDER_PP_DEF_8lcm ORDER_PP_FN( \

8fn(8X, 8Y, \

   8if(8or(8is_0(8X), 8is_0(8Y)),     \
       0,                             \
       8quotient(8times(8X, 8Y), 8gcd(8X, 8Y)))))

// No support for negative numbers

ORDER_PP( 8to_lit(8lcm(12, 18)) ) // 36</lang>

PARI/GP

Built-in function: <lang parigp>lcm</lang>

Pascal

<lang pascal>Program LeastCommonMultiple(output);

function lcm(a, b: longint): longint;

 begin
   lcm := a;
   while (lcm mod b) <> 0 do
     inc(lcm, a);
 end;

begin

 writeln('The least common multiple of 12 and 18 is: ', lcm(12, 18));

end.</lang> Output:

The least common multiple of 12 and 18 is: 36

Perl

Using GCD: <lang Perl>sub gcd { my ($a, $b) = @_; while ($a) { ($a, $b) = ($b % $a, $a) } $b }

sub lcm { my ($a, $b) = @_; ($a && $b) and $a / gcd($a, $b) * $b or 0 }

print lcm(1001, 221);</lang> Or by repeatedly increasing the smaller of the two until LCM is reached:<lang perl>sub lcm { use integer; my ($x, $y) = @_; my ($a, $b) = @_; while ($a != $b) { ($a, $b, $x, $y) = ($b, $a, $y, $x) if $a > $b; $a = $b / $x * $x; $a += $x if $a < $b; } $a }

print lcm(1001, 221);</lang>

Perl 6

This function is provided as an infix so that it can be used productively with various metaoperators. <lang Perl 6>say 3 lcm 4; # infix say [lcm] 1..20; # reduction say ~(1..10 Xlcm 1..10) # cross</lang> Output:

12
232792560
1 2 3 4 5 6 7 8 9 10 2 2 6 4 10 6 14 8 18 10 3 6 3 12 15 6 21 24 9 30 4 4 12 4 20 12 28 8 36 20 5 10 15 20 5 30 35 40 45 10 6 6 6 12 30 6 42 24 18 30 7 14 21 28 35 42 7 56 63 70 8 8 24 8 40 24 56 8 72 40 9 18 9 36 45 18 63 72 9 90 10 10 30 20 10 30 70 40 90 10

PHP

Translation of: D

<lang php>echo lcm(12, 18) == 36;

function lcm($m, $n) {

   if ($m == 0 || $n == 0) return 0;
   $r = ($m * $n) / gcd($m, $n);
   return abs($r);

}

function gcd($a, $b) {

   while ($b != 0) {
       $t = $b;
       $b = $a % $b;
       $a = $t;
   }
   return $a;

}</lang>

PicoLisp

Using 'gcd' from Greatest common divisor#PicoLisp: <lang PicoLisp>(de lcm (A B)

  (abs (*/ A B (gcd A B))) )</lang>

PL/I

<lang PL/I> /* Calculate the Least Common Multiple of two integers. */

LCM: procedure options (main); /* 16 October 2013 */

  declare (m, n) fixed binary (31);

  get (m, n);
  put edit ('The LCM of ', m, ' and ', n, ' is', LCM(m, n)) (a, x(1));

LCM: procedure (m, n) returns (fixed binary (31));

  declare (m, n) fixed binary (31) nonassignable;

  if m = 0 | n = 0 then return (0);
  return (abs(m*n) / GCD(m, n));

end LCM;

GCD: procedure (a, b) returns (fixed binary (31)) recursive;

  declare (a, b) fixed binary (31);

  if b = 0 then return (a);

  return (GCD (b, mod(a, b)) );

end GCD; end LCM; </lang>

The LCM of              14  and              35  is             70

Prolog

SWI-Prolog knows gcd. <lang Prolog>lcm(X, Y, Z) :- Z is abs(X * Y) / gcd(X,Y).</lang>

Example:

 ?- lcm(18,12, Z).
Z = 36.

PureBasic

<lang PureBasic>Procedure GCDiv(a, b); Euclidean algorithm

 Protected r
 While b
   r = b
   b = a%b
   a = r
 Wend
 ProcedureReturn a

EndProcedure

Procedure LCM(m,n)

 Protected t
 If m And n
   t=m*n/GCDiv(m,n)
 EndIf
 ProcedureReturn t*Sign(t)

EndProcedure</lang>

Python

gcd

Using the fractions libraries gcd function: <lang python>>>> import fractions >>> def lcm(a,b): return abs(a * b) / fractions.gcd(a,b) if a and b else 0

>>> lcm(12, 18) 36 >>> lcm(-6, 14) 42 >>> assert lcm(0, 2) == lcm(2, 0) == 0 >>> </lang>

Prime decomposition

This imports Prime decomposition#Python <lang python> import operator from prime_decomposition import decompose

def lcm(a, b):

   if a and b:
       da = list(decompose(abs(a)))
       db = list(decompose(abs(b)))
       merge= da
       for d in da:
           if d in db: db.remove(d)
       merge += db
       return reduce(operator.mul, merge, 1)
   return 0

if __name__ == '__main__':

   print( lcm(12, 18) )    # 36
   print( lcm(-6, 14) )    # 42
   assert lcm(0, 2) == lcm(2, 0) == 0</lang>

Iteration over multiples

<lang python>>>> def lcm(*values): values = set([abs(int(v)) for v in values]) if values and 0 not in values: n = n0 = max(values) values.remove(n) while any( n % m for m in values ): n += n0 return n return 0

>>> lcm(-6, 14) 42 >>> lcm(2, 0) 0 >>> lcm(12, 18) 36 >>> lcm(12, 18, 22) 396 >>> </lang>

Repeated modulo

Translation of: Tcl

<lang python>>>> def lcm(p,q): p, q = abs(p), abs(q) m = p * q if not m: return 0 while True: p %= q if not p: return m // q q %= p if not q: return m // p

>>> lcm(-6, 14) 42 >>> lcm(12, 18) 36 >>> lcm(2, 0) 0 >>> </lang>

Qi

<lang qi> (define gcd

 A 0 -> A
 A B -> (gcd B (MOD A B)))

(define lcm A B -> (/ (* A B) (gcd A B))) </lang>

R

<lang R> "%gcd%" <- function(u, v) {ifelse(u %% v != 0, v %gcd% (u%%v), v)}

"%lcm%" <- function(u, v) { abs(u*v)/(u %gcd% v)}

print (50 %lcm% 75) </lang>

Racket

Racket already has defined both lcm and gcd funtions: <lang Racket>#lang racket (lcm 3 4 5 6) ;returns 60 (lcm 8 108) ;returns 216 (gcd 8 108) ;returns 4 (gcd 108 216 432) ;returns 108</lang>

Retro

This is from the math extensions library included with Retro.

<lang Retro>: gcd ( ab-n ) [ tuck mod dup ] while drop ;

lcm ( ab-n ) 2over gcd [ * ] dip / ;</lang>

REXX

The LCM and GCD subroutines can handle any number of arguments. <lang rexx>/*REXX pgm finds LCM (Least Common Multiple) of a number of integers.*/ numeric digits 9000 /*handle nine-thousand digit nums*/

say 'the LCM of 19 & 0 is:' lcm(19 0) say 'the LCM of 0 & 85 is:' lcm( 0 85) say 'the LCM of 14 & -6 is:' lcm(14,-6) say 'the LCM of 18 & 12 is:' lcm(18 12) say 'the LCM of 18 & 12 & -5 is:' lcm(18 12,-5) say 'the LCM of 18 & 12 & -5 & 97 is:' lcm(18,12,-5,97) say 'the LCM of 2**19-1 & 2**521-1 is:' lcm(2**19-1 2**521-1)

                        /*──(above)── the 7th and 13th Mersenne primes.*/

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────LCM subroutine──────────────────────*/ lcm: procedure; $=; do j=1 for arg(); $=$ arg(j); end x=abs(word($,1)) /* [↑] build a list of arguments.*/

           do k=2  to words($);   !=abs(word($,k));  if !=0 then return 0
           x=x*! / gcd(x,!)           /*have  GCD do the heavy lifting.*/
           end   /*k*/

return x /*return with the money. */ /*──────────────────────────────────GCD subroutine──────────────────────*/ gcd: procedure; $=; do j=1 for arg(); $=$ arg(j); end parse var $ x z .; if x=0 then x=z /* [↑] build a list of arguments.*/ x=abs(x)

           do k=2  to words($);    y=abs(word($,k));  if y=0 then iterate
             do until _==0;   _=x//y;   x=y;   y=_;   end   /*until*/
           end   /*k*/

return x /*return with the money. */</lang>

Output:

the LCM of  19  &   0            is: 0
the LCM of   0  &  85            is: 0
the LCM of  14  &  -6            is: 42
the LCM of  18  &  12            is: 36
the LCM of  18  &  12  & -5      is: 180
the LCM of  18  &  12  & -5 & 97 is: 17460
the LCM of  2**19-1  &  2**521-1 is: 3599124170836896975638715824247986405702540425206233163175195063626010878994006898599180426323472024265381751210505324617708575722407440034562999570663839968526337

Ruby

Ruby has an Integer#lcm method, which finds the least common multiple of two integers.

<lang ruby>irb(main):001:0> require 'rational' => true irb(main):002:0> 12.lcm 18 => 36</lang>

I can also write my own lcm method. This one takes any number of arguments, and works by iterating the multiples of m until it finds a multiple of n.

<lang ruby>def lcm(*args)

 args.inject(1) do |m, n|
   next 0 if m == 0 or n == 0
   i = m
   loop do
     break i if i % n == 0
     i += m
   end
 end

end</lang>

Run BASIC

<lang runbasic>print lcm(22,44)

function lcm(m,n)

while n
  t = m
  m = n
  n = t mod n
wend

lcm = m end function</lang>

Scala

Scheme

Seed7

<lang seed7>$ include "seed7_05.s7i";

const func integer: gcd (in var integer: a, in var integer: b) is func

 result
   var integer: gcd is 0;
 local
   var integer: help is 0;
 begin
   while a <> 0 do
     help := b rem a;
     b := a;
     a := help;
   end while;
   gcd := b;
 end func;

const func integer: lcm (in integer: a, in integer: b) is

 return a div gcd(a, b) * b;

const proc: main is func

 begin
   writeln("lcm(35, 21) = " <& lcm(21, 35));
 end func;</lang>

Original source: [1]

Tcl

<lang tcl>proc lcm {p q} {

   set m [expr {$p * $q}]
   if {!$m} {return 0}
   while 1 {

set p [expr {$p % $q}] if {!$p} {return [expr {$m / $q}]} set q [expr {$q % $p}] if {!$q} {return [expr {$m / $p}]}

}</lang> Demonstration <lang tcl>puts [lcm 12 18]</lang> Output:

TI-83 BASIC

<lang ti83b>lcm(12, 18)

              36</lang>

TSE SAL

<lang TSESAL>// library: math: get: least: common: multiple <description></description> <version control></version control> <version>1.0.0.0.2</version> <version control></version control> (filenamemacro=getmacmu.s) [<Program>] [<Research>] [kn, ri, su, 20-01-2013 14:36:11] INTEGER PROC FNMathGetLeastCommonMultipleI( INTEGER x1I, INTEGER x2I )

//
RETURN( x1I * x2I / FNMathGetGreatestCommonDivisorI( x1I, x2I ) )
//

END

// library: math: get: greatest: common: divisor <description>greatest common divisor whole numbers. Euclid's algorithm. Recursive version</description> <version control></version control> <version>1.0.0.0.3</version> <version control></version control> (filenamemacro=getmacdi.s) [<Program>] [<Research>] [kn, ri, su, 20-01-2013 14:22:41] INTEGER PROC FNMathGetGreatestCommonDivisorI( INTEGER x1I, INTEGER x2I )

//
IF ( x2I == 0 )
 //
 RETURN( x1I )
 //
ENDIF
//
RETURN( FNMathGetGreatestCommonDivisorI( x2I, x1I MOD x2I ) )
//

END

PROC Main()

//
STRING s1[255] = "10"
STRING s2[255] = "20"
REPEAT
 IF ( NOT ( Ask( "math: get: least: common: multiple: x1I = ", s1, _EDIT_HISTORY_ ) ) AND ( Length( s1 ) > 0 ) ) RETURN() ENDIF
 IF ( NOT ( Ask( "math: get: least: common: multiple: x2I = ", s2, _EDIT_HISTORY_ ) ) AND ( Length( s2 ) > 0 ) ) RETURN() ENDIF
 Warn( FNMathGetLeastCommonMultipleI( Val( s1 ), Val( s2 ) ) ) // gives e.g. 10
UNTIL FALSE

END</lang>

UNIX Shell

$\operatorname {lcm} (m,n)=\left|{\frac {m\times n}{\operatorname {gcd} (m,n)}}\right|$

Works with: Bourne Shell

<lang bash>gcd() { # Calculate $1 % $2 until $2 becomes zero. until test 0 -eq "$2"; do # Parallel assignment: set -- 1 2 set -- "$2" "`expr "$1" % "$2"`" done

# Echo absolute value of $1. test 0 -gt "$1" && set -- "`expr 0 - "$1"`" echo "$1" }

lcm() { set -- "$1" "$2" "`gcd "$1" "$2"`" set -- "`expr "$1" \* "$2" / "$3"`" test 0 -gt "$1" && set -- "`expr 0 - "$1"`" echo "$1" }

lcm 30 -42

=> 210</lang>

C Shell

<lang csh>alias gcd eval \set gcd_args=( \!*:q ) \\ @ gcd_u=$gcd_args[2] \\ @ gcd_v=$gcd_args[3] \\ while ( $gcd_v != 0 ) \\ @ gcd_t = $gcd_u % $gcd_v \\ @ gcd_u = $gcd_v \\ @ gcd_v = $gcd_t \\ end \\ if ( $gcd_u < 0 ) @ gcd_u = - $gcd_u \\ @ $gcd_args[1]=$gcd_u \\ '\'

alias lcm eval \set lcm_args=( \!*:q ) \\ @ lcm_m = $lcm_args[2] \\ @ lcm_n = $lcm_args[3] \\ gcd lcm_d $lcm_m $lcm_n \\ @ lcm_r = ( $lcm_m * $lcm_n ) / $lcm_d \\ if ( $lcm_r < 0 ) @ lcm_r = - $lcm_r \\ @ $lcm_args[1] = $lcm_r \\ '\'

lcm result 30 -42 echo $result

=> 210</lang>

Vala

<lang vala> int lcm(int a, int b){

   /*Return least common multiple of two ints*/
   // check for 0's                                                            
   if (a == 0 || b == 0)

return 0;

   // Math.abs(x) only works for doubles, Math.absf(x) for floats              
   if (a < 0)
       a *= -1;
   if (b < 0)

b *= -1;

   int x = 1;
   while (true){
       if (a * x % b == 0)
           return a*x;
       x++;
   }

}

void main(){

   int	a = 12;
   int	b = 18;

   stdout.printf("lcm(%d, %d) = %d\n",	a, b, lcm(a, b));

} </lang>

Wortel

Operator <lang wortel>@lcm a b</lang> Number expression <lang wortel>!#~km a b</lang> Function (using gcd) <lang wortel>&[a b] *b /a @gcd a b</lang>

XPL0

<lang XPL0>include c:\cxpl\codes;

func GCD(M,N); \Return the greatest common divisor of M and N int M, N; int T; [while N do \Euclid's method

   [T:= M;  M:= N;  N:= rem(T/N)];

return M; ];

func LCM(M,N); \Return least common multiple int M, N; return abs(M*N) / GCD(M,N);

\Display the LCM of two integers entered on command line IntOut(0, LCM(IntIn(8), IntIn(8)))</lang>