View source for Least common multiple

{{task}}
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 &times; 3 = 36), and 18 is a factor (18 &times; 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''.

<math>\operatorname{lcm}(m, n) = \frac{|m \times n|}{\operatorname{gcd}(m, n)}</math>

One can also find ''lcm'' by merging the [[prime decomposition]]s of both ''m'' and ''n''.

References: [http://mathworld.wolfram.com/LeastCommonMultiple.html MathWorld], [[wp:Least common multiple|Wikipedia]].

=={{header|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 * 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:
<pre>LCM of 12, 18 is 36
LCM of -6, 14 is 42
LCM of 35, 0 is 0</pre>

=={{header|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>

=={{header|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: <pre>$ awk -f lcd.awk
12 18
36
-6 14
42
35 0
0
</pre>

=={{header|BBC BASIC}}==
{{Works with|BBC BASIC for Windows}}
<lang BBC BASIC>
      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>

=={{header|bc}}==
{{trans|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>

=={{header|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>

=={{header|C sharp|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>

=={{header|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>

=={{header|Common Lisp}}==
Common Lisp provides the <tt>lcm</tt> function. It can accept two or more (or less) parameters.

<lang lisp>CL-USER> (lcm 12 18)
36
CL-USER> (lcm 12 18 22)
396</lang>

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 <tt>lambda</tt> finds the least common multiple of two integers, and the <tt>reduce</tt> transforms it to accept any number of parameters. The <tt>reduce</tt> operation exploits how ''lcm'' is associative, <tt>(lcm a b c) == (lcm (lcm a b) c)</tt>; and how 1 is an identity, <tt>(lcm 1 a) == a</tt>.

=={{header|D}}==
<lang d>import std.stdio, std.bigint;

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

T gcd(T)(T a, T b) {
    while (b != 0) {
        auto t = b;
        b = a % b;
        a = t;
    }
    return a;
}

void main() {
    writeln(lcm(12, 18));
    writeln(lcm(BigInt("2562047788015215500854906332309589561"),
                BigInt("6795454494268282920431565661684282819")));
}</lang>
Output:
<pre>36
15669251240038298262232125175172002594731206081193527869</pre>

=={{header|DWScript}}==
<lang delphi>PrintLn(Lcm(12, 18));</lang>
Output:
<pre>36</pre>

=={{header|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>

=={{header|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>

=={{header|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>

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

=={{header|GAP}}==
<lang gap># Built-in
LcmInt(12, 18);
# 36</lang>

=={{header|Go}}==
<lang go>package main

import (
    "fmt"
    "math/big"
)

var m, n big.Int

func init() {
    m.SetString("2562047788015215500854906332309589561", 10)
    n.SetString("6795454494268282920431565661684282819", 10)
}

func main() {
    var d big.Int
    big.GcdInt(&d, nil, nil, &m, &n)
    fmt.Println(d.Mul(d.Div(&m, &d), &n))
}</lang>
Output:
<pre>
15669251240038298262232125175172002594731206081193527869
</pre>

=={{header|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>

=={{header|Icon}} and {{header|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>

{{libheader|Icon Programming Library}}  
[http://www.cs.arizona.edu/icon/library/src/procs/numbers.icn 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>

=={{header|J}}==
J provides the dyadic verb <code>*.</code> 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>

=={{header|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>

=={{header|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>

=={{header|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>

=={{header|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:

<pre>874</pre>

=={{header|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>

=={{header|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>

=={{header|PARI/GP}}==
Built-in function:
<lang parigp>lcm</lang>

=={{header|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>

=={{header|Perl 6}}==
This function is provided as an infix so that it can be used productively with various metaoperators.
<lang>say 3 lcm 4;            # infix
say [lcm] 1..20;        # reduction
say ~(1..10 Xlcm 1..10) # cross</lang>
Output:
<pre>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</pre>

=={{header|PHP}}==
{{trans|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>

=={{header|PicoLisp}}==
Using 'gcd' from [[Greatest common divisor#PicoLisp]]:
<lang PicoLisp>(de lcm (A B)
   (abs (*/ A B (gcd A B))) )</lang>

=={{header|Prolog}}==
SWI-Prolog knows gcd.
<lang Prolog>lcm(X, Y, Z) :-
	Z is abs(X * Y) / gcd(X,Y).
</lang>
Example :
<pre> ?- lcm(18,12, Z).
Z = 36.
</pre>
=={{header|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>

=={{header|Python}}==
===gcd===
Using the fractions libraries [http://docs.python.org/library/fractions.html?highlight=fractions.gcd#fractions.gcd 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===
{{trans|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>

=={{header|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>

=={{header|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>

=={{header|Ruby}}==
Ruby has an <tt>Integer#lcm</tt> 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 <tt>lcm</tt> 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>

<lang ruby>irb(main):004:0> lcm 12, 18
=> 36
irb(main):005:0> lcm 12, 18, 22
=> 396</lang>

=={{header|Scala}}==
<lang scala>def gcd(a: Int, b: Int):Int=if (b==0) a.abs else gcd(b, a%b)
def lcm(a: Int, b: Int)=(a*b).abs/gcd(a,b)</lang>
<lang scala>lcm(12, 18)   // 36
lcm( 2,  0)   // 0
lcm(-6, 14)   // 42</lang>

=={{header|Scheme}}==
<lang scheme>> (lcm 108 8)
216</lang>

=={{header|Seed7}}==
<lang seed7>$ include "seed7_05.s7i";

const func integer: gcd (in var integer: a, in var integer: b) is func
  result
    var integer: result is 0;
  local
    var integer: help is 0;
  begin
    while a <> 0 do
      help := b rem a;
      b := a;
      a := help;
    end while;
    result := 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: [http://seed7.sourceforge.net/algorith/math.htm#lcm]

=={{header|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:
 36

=={{header|TI-83 BASIC}}==
<lang ti83b>lcm(12, 18)
               36</lang>

=={{header|UNIX Shell}}==
<math>\operatorname{lcm}(m, n) = \left | \frac{m \times n}{\operatorname{gcd}(m, n)} \right |</math>

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

==={{header|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>

=={{header|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>