Least common multiple

From Rosetta Code
Jump to: navigation, search
Task
Least common multiple
You are encouraged to solve this task according to the task description, using any language you may know.

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.

Contents

[edit] Ada

lcm_test.adb:

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;

Output:

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

[edit] 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)

[edit] 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
 

Example

 
ConsoleWrite(_LCM(12,18) & @LF)
ConsoleWrite(_LCM(-5,12) & @LF)
ConsoleWrite(_LCM(13,0) & @LF)
 
36
60
0

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

[edit] 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) }
Example input and output:
$ awk -f lcd.awk
12 18
36
-6 14
42
35 0
0

[edit] BASIC

[edit] Applesoft BASIC

ported from BBC BASIC

10 DEF FN MOD(A) = INT((A / B - INT(A / B)) * B + .05) * SGN(A / B)
20 INPUT"M=";M%
30 INPUT"N=";N%
40 GOSUB 100
50 PRINT R
60 END
 
100 REM LEAST COMMON MULTIPLE M% N%
110 R = 0
120 IF M% = 0 OR N% = 0 THEN RETURN
130 A% = M% : B% = N% : GOSUB 200"GCD
140 R = ABS(M%*N%)/R
150 RETURN
 
200 REM GCD ITERATIVE EUCLID A% B%
210 FOR B = B% TO 0 STEP 0
220 C% = A%
230 A% = B
240 B = FN MOD(C%)
250 NEXT B
260 R = ABS(A%)
270 RETURN

[edit] 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%)
 

[edit] bc

Translation of: AWK
/* 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)
}

[edit] Bracmat

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

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

Output:

36 42 35 234

[edit] 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;
}

[edit] C++

Library: Boost
#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 ;
}
Output:
The least common multiple of 12 and 18 is 36 ,
and the greatest common divisor 6 !

[edit] C#

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;
}

[edit] Clojure

(defn gcd 
[a b]
(if (zero? b)
a
(recur b, (mod a b))))
 
(defn lcm
[a b]
(/ (* a b) (gcd a b)))

[edit] 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.

[edit] Common Lisp

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

CL-USER> (lcm 12 18)
36
CL-USER> (lcm 12 18 22)
396

Here is one way to reimplement it.

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

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.

[edit] 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;
}
Output:
36
15669251240038298262232125175172002594731206081193527869

[edit] DWScript

PrintLn(Lcm(12, 18));

Output:

36

[edit] 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)).
Output:
12

[edit] 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

[edit] Excel

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

 
=LCM(A1:J1)
 

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

 
12 3 5 23 13 67 15 9 4 2
 
3605940
 

[edit] Ezhil

 
## இந்த நிரல் இரு எண்களுக்கு இடையிலான மீச்சிறு பொது மடங்கு (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) = ", மீபொம(அ, ஆ)
 


[edit] F#

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)

[edit] Factor

The vocabulary math.functions already provides lcm.

USING: math.functions prettyprint ;
26 28 lcm .

This program outputs 364.

One can also reimplement lcm.

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 .

[edit] 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 */ ;

[edit] Frink

Frink has a built-in LCM function that handles arbitrarily-large integers.

 
println[lcm[2562047788015215500854906332309589561, 6795454494268282920431565661684282819]]
 

[edit] FunL

FunL has function lcm in module integers with the following implement:

def
lcm( _, 0 ) = 0
lcm( 0, _ ) = 0
lcm( x, y ) = abs( (x\gcd(x, y)) y )

[edit] GAP

# Built-in
LcmInt(12, 18);
# 36

[edit] 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))
}
Output:
15669251240038298262232125175172002594731206081193527869

[edit] Haskell

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

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

[edit] Icon and Unicon

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

link numbers 
procedure main()
write("lcm of 18, 36 = ",lcm(18,36))
write("lcm of 0, 9 36 = ",lcm(0,9))
end

numbers provides lcm and gcd and looks like this:

procedure lcm(i, j)		#: least common multiple
if (i = 0) | (j = 0) then return 0
return abs(i * j) / gcd(i, j)
end

[edit] J

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

      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

[edit] 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);
}
}

[edit] JavaScript

Computing the least common multiple of an integer array, using the associative law:

\operatorname{lcm}(a,b,c)=\operatorname{lcm}(\operatorname{lcm}(a,b),c),

\operatorname{lcm}(a_1,a_2,\ldots,a_n) = \operatorname{lcm}(\operatorname{lcm}(a_1,a_2,\ldots,a_{n-1}),a_n).

function LCM(A)  // A is an integer array (e.g. [-50,25,-45,-18,90,447])
{
var n = A.length, a = Math.abs(A[0]);
for (var i = 1; i < n; i++)
{ var b = Math.abs(A[i]), c = a;
while (a && b){ a > b ? a %= b : b %= a; }
a = Math.abs(c*A[i])/(a+b);
}
return a;
}
 
/* For example:
LCM([-50,25,-45,-18,90,447]) -> 67050
*/

[edit] Julia

Built-in function:

lcm(m,n)

[edit] 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

[edit] 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.
LabVIEW Least common multiple.png


[edit] 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)
Output:
42
0
36
132
217

[edit] Liberty BASIC

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
 

[edit]

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

Demo code:

print lcm 38 46

Output:

874

[edit] 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) )

[edit] 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.

> ilcm( 12, 18 );
36
 

[edit] Mathematica

LCM[18,12]
-> 36

[edit] MATLAB / Octave

 lcm(a,b) 

[edit] 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))

[edit] МК-61/52

ИПA	ИПB	*	|x|	ПC	ИПA	ИПB	/	[x]	П9
ИПA ИПB ПA ИП9 * - ПB x=0 05 ИПC
ИПA / С/П

[edit] NetRexx

/* NetRexx */
options replace format comments java crossref symbols nobinary
 
numeric digits 3000
 
runSample(arg)
return
 
-- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
method lcm(m_, n_) public static
L_ = m_ * n_ % gcd(m_, n_)
return L_
 
-- ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
-- Euclid's algorithm - iterative implementation
method gcd(m_, n_) public static
loop while n_ > 0
c_ = m_ // n_
m_ = n_
n_ = c_
end
return m_
 
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
method runSample(arg) private static
parse arg samples
if samples = '' | samples = '.' then
samples = '-6 14 = 42 |' -
'3 4 = 12 |' -
'18 12 = 36 |' -
'2 0 = 0 |' -
'0 85 = 0 |' -
'12 18 = 36 |' -
'5 12 = 60 |' -
'12 22 = 132 |' -
'7 31 = 217 |' -
'117 18 = 234 |' -
'38 46 = 874 |' -
'18 12 -5 = 180 |' -
'-5 18 12 = 180 |' - -- confirm that other permutations work
'12 -5 18 = 180 |' -
'18 12 -5 97 = 17460 |' -
'30 42 = 210 |' -
'30 42 = . |' - -- 210; no verification requested
'18 12' -- 36
 
loop while samples \= ''
parse samples sample '|' samples
loop while sample \= ''
parse sample mnvals '=' chk sample
if chk = '' then chk = '.'
mv = mnvals.word(1)
loop w_ = 2 to mnvals.words mnvals
nv = mnvals.word(w_)
mv = mv.abs
nv = nv.abs
mv = lcm(mv, nv)
end w_
lv = mv
select case chk
when '.' then state = ''
when lv then state = '(verified)'
otherwise state = '(failed)'
end
mnvals = mnvals.space(1, ',').changestr(',', ', ')
say 'lcm of' mnvals.right(15.max(mnvals.length)) 'is' lv.right(5.max(lv.length)) state
end
end
 
return
 
Output:
lcm of          -6, 14 is    42 (verified)
lcm of            3, 4 is    12 (verified)
lcm of          18, 12 is    36 (verified)
lcm of            2, 0 is     0 (verified)
lcm of           0, 85 is     0 (verified)
lcm of          12, 18 is    36 (verified)
lcm of           5, 12 is    60 (verified)
lcm of          12, 22 is   132 (verified)
lcm of           7, 31 is   217 (verified)
lcm of         117, 18 is   234 (verified)
lcm of          38, 46 is   874 (verified)
lcm of      18, 12, -5 is   180 (verified)
lcm of      -5, 18, 12 is   180 (verified)
lcm of      12, -5, 18 is   180 (verified)
lcm of  18, 12, -5, 97 is 17460 (verified)
lcm of          30, 42 is   210 (verified)
lcm of          30, 42 is   210 
lcm of          18, 12 is    36

[edit] Nimrod

proc gcd(u, v): auto =
var
t = 0
u = u
v = v
while v != 0:
t = u
u = v
v = t %% v
abs(u)
 
proc lcm(a, b): auto = abs(a * b) div gcd(a, b)
 
echo lcm(12, 18)
echo lcm(-6, 14)

[edit] Objeck

Translation of: C
 
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;
}
}
 

[edit] 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)

[edit] 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
 

[edit] Order

Translation of: bc
#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

[edit] PARI/GP

Built-in function:

lcm

[edit] 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.

Output:

The least common multiple of 12 and 18 is: 36

[edit] Perl

Using GCD:

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);
Or by repeatedly increasing the smaller of the two until LCM is reached:
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);

[edit] Perl 6

This function is provided as an infix so that it can be used productively with various metaoperators.

say 3 lcm 4;            # infix
say [lcm] 1..20; # reduction
say ~(1..10 Xlcm 1..10) # cross

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

[edit] PHP

Translation of: D
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;
}

[edit] PicoLisp

Using 'gcd' from Greatest common divisor#PicoLisp:

(de lcm (A B)
(abs (*/ A B (gcd A B))) )

[edit] 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;
 
The LCM of              14  and              35  is             70

[edit] Prolog

SWI-Prolog knows gcd.

lcm(X, Y, Z) :-
Z is abs(X * Y) / gcd(X,Y).

Example:

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

[edit] 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

[edit] Python

[edit] gcd

Using the fractions libraries gcd function:

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

[edit] Prime decomposition

This imports Prime decomposition#Python

from prime_decomposition import decompose
try:
reduce
except NameError:
from functools import reduce
 
def lcm(a, b):
mul = int.__mul__
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(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

[edit] Iteration over multiples

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

[edit] Repeated modulo

Translation of: Tcl
>>> 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
>>>

[edit] Qi

 
(define gcd
A 0 -> A
A B -> (gcd B (MOD A B)))
 
(define lcm A B -> (/ (* A B) (gcd A B)))
 

[edit] 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)
 

[edit] Racket

Racket already has defined both lcm and gcd funtions:

#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

[edit] Retro

This is from the math extensions library included with Retro.

: gcd ( ab-n ) [ tuck mod dup ] while drop ;
: lcm ( ab-n ) 2over gcd [ * ] dip / ;

[edit] REXX

The LCM and GCD subroutines can handle any number of arguments.

/*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. */
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

[edit] Ruby

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

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

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.

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
irb(main):004:0> lcm 12, 18
=> 36
irb(main):005:0> lcm 12, 18, 22
=> 396

[edit] Run BASIC

print lcm(22,44)
 
function lcm(m,n)
while n
t = m
m = n
n = t mod n
wend
lcm = m
end function

[edit] 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)
lcm(12, 18)   // 36
lcm( 2, 0) // 0
lcm(-6, 14) // 42

[edit] Scheme

> (lcm 108 8)
216

[edit] 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;

Original source: [1]

[edit] Smalltalk

Smalltalk has a built-in lcm method on SmallInteger:

12 lcm: 18

[edit] Sparkling

function factors(n) {
var f = {};
 
for var i = 2; n > 1; i++ {
while n % i == 0 {
n /= i;
f[i] = f[i] != nil ? f[i] + 1 : 1;
}
}
 
return f;
}
 
function GCD(n, k) {
let f1 = factors(n);
let f2 = factors(k);
 
let fs = map(f1, function(factor, multiplicity) {
let m = f2[factor];
return m == nil ? 0 : min(m, multiplicity);
});
 
let rfs = {};
foreach(fs, function(k, v) {
rfs[sizeof rfs] = pow(k, v);
});
 
return reduce(rfs, 1, function(x, y) { return x * y; });
}
 
function LCM(n, k) {
return n * k / GCD(n, k);
}

[edit] 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}]}
}
}

Demonstration

puts [lcm 12 18]

Output:

36

[edit] TI-83 BASIC

lcm(12, 18)
36

[edit] TSE SAL

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


[edit] UNIX Shell

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

Works with: Bourne Shell
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

[edit] C Shell

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

[edit] 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));
}
 

[edit] Wortel

Operator

@lcm a b

Number expression

!#~km a b

Function (using gcd)

&[a b] *b /a @gcd a b

[edit] 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)))

[edit] zkl

fcn gcd(a,b){while(b){t:=a; a=b; b=t%b} a.abs()}
fcn lcm(m,n){(m*n).abs()/gcd(m,n)}
Output:
zkl: lcm(12,18)
36
zkl: lcm(-6,14)
42
zkl: lcm(35,0)
0
Personal tools
Namespaces

Variants
Actions
Community
Explore
Misc
Toolbox