Least common multiple: Difference between revisions
m →{{header|zkl}}: update |
PascalABC.NET |
||
(101 intermediate revisions by 47 users not shown) | |||
Line 1: | Line 1: | ||
[[Category:Recursion]] |
|||
{{task}} |
{{task}} |
||
;Task: |
;Task: |
||
Compute the least common multiple of two integers. |
Compute the least common multiple (LCM) of two integers. |
||
Given ''m'' and ''n'', the least common multiple is the smallest positive integer that has both ''m'' and ''n'' as factors. |
Given ''m'' and ''n'', the least common multiple is the smallest positive integer that has both ''m'' and ''n'' as factors. |
||
Line 8: | Line 10: | ||
;Example: |
;Example: |
||
The least common multiple of |
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''. |
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''. |
||
Line 21: | Line 30: | ||
;Related task |
|||
;References: |
|||
:* [https://rosettacode.org/wiki/Greatest_common_divisor greatest common divisor]. |
|||
* [http://mathworld.wolfram.com/LeastCommonMultiple.html MathWorld]. |
|||
* [[wp:Least common multiple|Wikipedia]]. |
|||
;See also: |
|||
* MathWorld entry: [http://mathworld.wolfram.com/LeastCommonMultiple.html Least Common Multiple]. |
|||
* Wikipedia entry: [[wp:Least common multiple|Least common multiple]]. |
|||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
<syntaxhighlight lang="11l">F gcd(=a, =b) |
|||
L b != 0 |
|||
(a, b) = (b, a % b) |
|||
R a |
|||
F lcm(m, n) |
|||
R m I/ gcd(m, n) * n |
|||
print(lcm(12, 18))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
36 |
|||
</pre> |
|||
=={{header|360 Assembly}}== |
|||
{{trans|PASCAL}} |
|||
For maximum compatibility, this program uses only the basic instruction set (S/360) |
|||
with 2 ASSIST macros (XDECO,XPRNT). |
|||
<syntaxhighlight lang="360asm">LCM CSECT |
|||
USING LCM,R15 use calling register |
|||
L R6,A a |
|||
L R7,B b |
|||
LR R8,R6 c=a |
|||
LOOPW LR R4,R8 c |
|||
SRDA R4,32 shift to next reg |
|||
DR R4,R7 c/b |
|||
LTR R4,R4 while c mod b<>0 |
|||
BZ ELOOPW leave while |
|||
AR R8,R6 c+=a |
|||
B LOOPW end while |
|||
ELOOPW LPR R9,R6 c=abs(u) |
|||
L R1,A a |
|||
XDECO R1,XDEC edit a |
|||
MVC PG+4(5),XDEC+7 move a to buffer |
|||
L R1,B b |
|||
XDECO R1,XDEC edit b |
|||
MVC PG+10(5),XDEC+7 move b to buffer |
|||
XDECO R8,XDEC edit c |
|||
MVC PG+17(10),XDEC+2 move c to buffer |
|||
XPRNT PG,80 print buffer |
|||
XR R15,R15 return code =0 |
|||
BR R14 return to caller |
|||
A DC F'1764' a |
|||
B DC F'3920' b |
|||
PG DC CL80'lcm(00000,00000)=0000000000' buffer |
|||
XDEC DS CL12 temp for edit |
|||
YREGS |
|||
END LCM</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
lcm( 1764, 3920)= 35280 |
|||
</pre> |
|||
=={{header|8th}}== |
=={{header|8th}}== |
||
< |
<syntaxhighlight lang="forth"> |
||
: gcd \ a b -- gcd |
: gcd \ a b -- gcd |
||
dup 0 n:= if drop ;; then |
dup 0 n:= if drop ;; then |
||
Line 52: | Line 120: | ||
bye</ |
bye</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>LCM of 18 and 12 = 36 |
<pre>LCM of 18 and 12 = 36 |
||
Line 59: | Line 127: | ||
</pre> |
</pre> |
||
=={{header|Action!}}== |
|||
<syntaxhighlight lang="action!">CARD FUNC Lcm(CARD a,b) |
|||
CARD tmp,c |
|||
IF a=0 OR b=0 THEN |
|||
RETURN (0) |
|||
FI |
|||
IF a<b THEN |
|||
tmp=a a=b b=tmp |
|||
FI |
|||
c=0 |
|||
DO |
|||
c==+1 |
|||
UNTIL a*c MOD b=0 |
|||
OD |
|||
RETURN(a*c) |
|||
PROC Test(CARD a,b) |
|||
CARD res |
|||
res=Lcm(a,b) |
|||
PrintF("LCM of %I and %I is %I%E",a,b,res) |
|||
RETURN |
|||
PROC Main() |
|||
Test(4,6) |
|||
Test(120,77) |
|||
Test(24,8) |
|||
Test(1,56) |
|||
Test(12,0) |
|||
RETURN</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Least_common_multiple.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
LCM of 4 and 6 is 12 |
|||
LCM of 120 and 77 is 9240 |
|||
LCM of 24 and 8 is 24 |
|||
LCM of 1 and 56 is 56 |
|||
LCM of 12 and 0 is 0 |
|||
</pre> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
lcm_test.adb: |
lcm_test.adb: |
||
< |
<syntaxhighlight lang="ada">with Ada.Text_IO; use Ada.Text_IO; |
||
procedure Lcm_Test is |
procedure Lcm_Test is |
||
Line 89: | Line 199: | ||
Put_Line ("LCM of -6, 14 is" & Integer'Image (Lcm (-6, 14))); |
Put_Line ("LCM of -6, 14 is" & Integer'Image (Lcm (-6, 14))); |
||
Put_Line ("LCM of 35, 0 is" & Integer'Image (Lcm (35, 0))); |
Put_Line ("LCM of 35, 0 is" & Integer'Image (Lcm (35, 0))); |
||
end Lcm_Test;</ |
end Lcm_Test;</syntaxhighlight> |
||
Output: |
Output: |
||
Line 97: | Line 207: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
< |
<syntaxhighlight lang="algol68"> |
||
BEGIN |
BEGIN |
||
PROC gcd = (INT m, n) INT : |
PROC gcd = (INT m, n) INT : |
||
Line 113: | Line 223: | ||
"and their greatest common divisor is", gcd(m,n))) |
"and their greatest common divisor is", gcd(m,n))) |
||
END |
END |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 123: | Line 233: | ||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
< |
<syntaxhighlight lang="algolw">begin |
||
integer procedure gcd ( integer value a, b ) ; |
integer procedure gcd ( integer value a, b ) ; |
||
if b = 0 then a else gcd( b, a rem abs(b) ); |
if b = 0 then a else gcd( b, a rem abs(b) ); |
||
Line 131: | Line 241: | ||
write( lcm( 15, 20 ) ); |
write( lcm( 15, 20 ) ); |
||
end.</ |
end.</syntaxhighlight> |
||
=={{header|APL}}== |
=={{header|APL}}== |
||
APL provides this function. |
APL provides this function. |
||
< |
<syntaxhighlight lang="apl"> 12^18 |
||
36</ |
36</syntaxhighlight> |
||
If for any reason we wanted to reimplement it, we could do so in terms of the greatest common divisor by transcribing the formula set out in the task specification into APL notation: |
If for any reason we wanted to reimplement it, we could do so in terms of the greatest common divisor by transcribing the formula set out in the task specification into APL notation: |
||
< |
<syntaxhighlight lang="apl"> LCM←{(|⍺×⍵)÷⍺∨⍵} |
||
12 LCM 18 |
12 LCM 18 |
||
36</ |
36</syntaxhighlight> |
||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
<syntaxhighlight lang="applescript">------------------ LEAST COMMON MULTIPLE ----------------- |
|||
<lang AppleScript>-- lcm :: Integral a => a -> a -> a |
|||
-- lcm :: Integral a => a -> a -> a |
|||
on lcm(x, y) |
on lcm(x, y) |
||
if |
if 0 = x or 0 = y then |
||
0 |
0 |
||
else |
else |
||
Line 154: | Line 266: | ||
--------------------------- TEST ------------------------- |
|||
-- TEST |
|||
on run |
on run |
||
Line 163: | Line 275: | ||
-- |
-------------------- GENERIC FUNCTIONS ------------------- |
||
-- abs :: Num a => a -> a |
-- abs :: Num a => a -> a |
||
on abs(x) |
on abs(x) |
||
if |
if 0 > x then |
||
-x |
-x |
||
else |
else |
||
Line 173: | Line 285: | ||
end if |
end if |
||
end abs |
end abs |
||
-- gcd :: Integral a => a -> a -> a |
-- gcd :: Integral a => a -> a -> a |
||
on gcd(x, y) |
on gcd(x, y) |
||
script |
script |
||
on |
on |λ|(a, b) |
||
if |
if 0 = b then |
||
a |
a |
||
else |
else |
||
|λ|(b, a mod b) |
|||
end if |
end if |
||
end |
end |λ| |
||
end script |
end script |
||
result's |λ|(abs(x), abs(y)) |
|||
end gcd</ |
end gcd</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<syntaxhighlight lang="applescript">36</syntaxhighlight> |
|||
<lang AppleScript>36</lang> |
|||
=={{header|Arendelle}}== |
=={{header|Arendelle}}== |
||
Line 205: | Line 317: | ||
)</pre> |
)</pre> |
||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="rebol">lcm: function [x,y][ |
|||
x * y / gcd @[x y] |
|||
] |
|||
print lcm 12 18</syntaxhighlight> |
|||
{{out}} |
|||
<pre>36</pre> |
|||
=={{header|Assembly}}== |
=={{header|Assembly}}== |
||
==={{header|x86 Assembly}}=== |
==={{header|x86 Assembly}}=== |
||
< |
<syntaxhighlight lang="asm"> |
||
; lcm.asm: calculates the least common multiple |
; lcm.asm: calculates the least common multiple |
||
; of two positive integers |
; of two positive integers |
||
Line 300: | Line 422: | ||
ret |
ret |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|ATS}}== |
|||
Compile with ‘patscc -o lcm lcm.dats’ |
|||
<syntaxhighlight lang="ats">#define ATS_DYNLOADFLAG 0 (* No initialization is needed. *) |
|||
#include "share/atspre_define.hats" |
|||
#include "share/atspre_staload.hats" |
|||
(********************************************************************) |
|||
(* *) |
|||
(* Declarations. *) |
|||
(* *) |
|||
(* (These could be ported to a .sats file.) *) |
|||
(* *) |
|||
(* lcm for unsigned integer types without constraints. *) |
|||
extern fun {tk : tkind} |
|||
g0uint_lcm (u : g0uint tk, |
|||
v : g0uint tk) :<> |
|||
g0uint tk |
|||
(* The gcd template function to be expanded when g0uint_lcm is |
|||
expanded. Set it to your favorite gcd function. *) |
|||
extern fun {tk : tkind} |
|||
g0uint_lcm$gcd (u : g0uint tk, |
|||
v : g0uint tk) :<> |
|||
g0uint tk |
|||
(* lcm for signed integer types, giving unsigned results. *) |
|||
extern fun {tk_signed, tk_unsigned : tkind} |
|||
g0int_lcm (u : g0int tk_signed, |
|||
v : g0int tk_signed) :<> |
|||
g0uint tk_unsigned |
|||
overload lcm with g0uint_lcm |
|||
overload lcm with g0int_lcm |
|||
(********************************************************************) |
|||
(* *) |
|||
(* The implementations. *) |
|||
(* *) |
|||
implement {tk} |
|||
g0uint_lcm (u, v) = |
|||
let |
|||
val d = g0uint_lcm$gcd<tk> (u, v) |
|||
in |
|||
(* There is no need to take the absolute value, because this |
|||
implementation is strictly for unsigned integers. *) |
|||
(u * v) / d |
|||
end |
|||
implement {tk_signed, tk_unsigned} |
|||
g0int_lcm (u, v) = |
|||
let |
|||
extern castfn |
|||
unsigned : |
|||
g0int tk_signed -<> g0uint tk_unsigned |
|||
in |
|||
g0uint_lcm (unsigned (abs u), unsigned (abs v)) |
|||
end |
|||
(********************************************************************) |
|||
(* *) |
|||
(* A test that it actually works. *) |
|||
(* *) |
|||
implement |
|||
main0 () = |
|||
let |
|||
implement {tk} |
|||
g0uint_lcm$gcd (u, v) = |
|||
(* An ugly gcd for the sake of demonstrating that it can be done |
|||
this way: Euclid’s algorithm written an the ‘Algol’ style, |
|||
which is not a natural style in ATS. Almost always you want |
|||
to write a tail-recursive function, instead. I did, however |
|||
find the ‘Algol’ style very useful when I was migrating |
|||
matrix routines from Fortran. |
|||
In reality, you would implement g0uint_lcm$gcd by having it |
|||
simply call whatever gcd template function you are using in |
|||
your program. *) |
|||
$effmask_all |
|||
begin |
|||
let |
|||
var x : g0uint tk = u |
|||
var y : g0uint tk = v |
|||
in |
|||
while (y <> 0) |
|||
let |
|||
val z = y |
|||
in |
|||
y := x mod z; |
|||
x := z |
|||
end; |
|||
x |
|||
end |
|||
end |
|||
in |
|||
assertloc (lcm (~6, 14) = 42U); |
|||
assertloc (lcm (2L, 0L) = 0ULL); |
|||
assertloc (lcm (12UL, 18UL) = 36UL); |
|||
assertloc (lcm (12, 22) = 132ULL); |
|||
assertloc (lcm (7ULL, 31ULL) = 217ULL) |
|||
end</syntaxhighlight> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">LCM(Number1,Number2) |
||
{ |
{ |
||
If (Number1 = 0 || Number2 = 0) |
If (Number1 = 0 || Number2 = 0) |
||
Line 316: | Line 544: | ||
Num1 = 12 |
Num1 = 12 |
||
Num2 = 18 |
Num2 = 18 |
||
MsgBox % LCM(Num1,Num2)</ |
MsgBox % LCM(Num1,Num2)</syntaxhighlight> |
||
=={{header|AutoIt}}== |
=={{header|AutoIt}}== |
||
<syntaxhighlight lang="autoit"> |
|||
<lang AutoIt> |
|||
Func _LCM($a, $b) |
Func _LCM($a, $b) |
||
Local $c, $f, $m = $a, $n = $b |
Local $c, $f, $m = $a, $n = $b |
||
Line 333: | Line 561: | ||
Return $m * $n / $b |
Return $m * $n / $b |
||
EndFunc ;==>_LCM |
EndFunc ;==>_LCM |
||
</syntaxhighlight> |
|||
</lang> |
|||
Example |
Example |
||
<syntaxhighlight lang="autoit"> |
|||
<lang AutoIt> |
|||
ConsoleWrite(_LCM(12,18) & @LF) |
ConsoleWrite(_LCM(12,18) & @LF) |
||
ConsoleWrite(_LCM(-5,12) & @LF) |
ConsoleWrite(_LCM(-5,12) & @LF) |
||
ConsoleWrite(_LCM(13,0) & @LF) |
ConsoleWrite(_LCM(13,0) & @LF) |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
36 |
36 |
||
Line 346: | Line 574: | ||
</pre> |
</pre> |
||
--[[User:BugFix|BugFix]] ([[User talk:BugFix|talk]]) 14:32, 15 November 2013 (UTC) |
--[[User:BugFix|BugFix]] ([[User talk:BugFix|talk]]) 14:32, 15 November 2013 (UTC) |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
< |
<syntaxhighlight lang="awk"># greatest common divisor |
||
function gcd(m, n, t) { |
function gcd(m, n, t) { |
||
# Euclid's method |
# Euclid's method |
||
Line 368: | Line 597: | ||
# Read two integers from each line of input. |
# Read two integers from each line of input. |
||
# Print their least common multiple. |
# Print their least common multiple. |
||
{ print lcm($1, $2) }</ |
{ print lcm($1, $2) }</syntaxhighlight> |
||
Example input and output: <pre>$ awk -f lcd.awk |
Example input and output: <pre>$ awk -f lcd.awk |
||
Line 383: | Line 612: | ||
==={{header|Applesoft BASIC}}=== |
==={{header|Applesoft BASIC}}=== |
||
ported from BBC BASIC |
ported from BBC BASIC |
||
< |
<syntaxhighlight lang="applesoftbasic">10 DEF FN MOD(A) = INT((A / B - INT(A / B)) * B + .05) * SGN(A / B) |
||
20 INPUT"M=";M% |
20 INPUT"M=";M% |
||
30 INPUT"N=";N% |
30 INPUT"N=";N% |
||
Line 404: | Line 633: | ||
250 NEXT B |
250 NEXT B |
||
260 R = ABS(A%) |
260 R = ABS(A%) |
||
270 RETURN</ |
270 RETURN</syntaxhighlight> |
||
==={{header|BBC BASIC}}=== |
==={{header|BBC BASIC}}=== |
||
{{Works with|BBC BASIC for Windows}} |
{{Works with|BBC BASIC for Windows}} |
||
<syntaxhighlight lang="bbc basic"> |
|||
<lang BBC BASIC> |
|||
DEF FN_LCM(M%,N%) |
DEF FN_LCM(M%,N%) |
||
IF M%=0 OR N%=0 THEN =0 ELSE =ABS(M%*N%)/FN_GCD_Iterative_Euclid(M%, N%) |
IF M%=0 OR N%=0 THEN =0 ELSE =ABS(M%*N%)/FN_GCD_Iterative_Euclid(M%, N%) |
||
Line 420: | Line 649: | ||
ENDWHILE |
ENDWHILE |
||
= ABS(A%) |
= ABS(A%) |
||
</syntaxhighlight> |
|||
</lang> |
|||
==={{header|IS-BASIC}}=== |
|||
<syntaxhighlight lang="is-basic">100 DEF LCM(A,B)=(A*B)/GCD(A,B) |
|||
110 DEF GCD(A,B) |
|||
120 DO WHILE B>0 |
|||
130 LET T=B:LET B=MOD(A,B):LET A=T |
|||
140 LOOP |
|||
150 LET GCD=A |
|||
160 END DEF |
|||
170 PRINT LCM(12,18)</syntaxhighlight> |
|||
==={{header|Tiny BASIC}}=== |
|||
{{works with|TinyBasic}} |
|||
<syntaxhighlight lang="basic">10 PRINT "First number" |
|||
20 INPUT A |
|||
30 PRINT "Second number" |
|||
40 INPUT B |
|||
42 LET Q = A |
|||
44 LET R = B |
|||
50 IF Q<0 THEN LET Q=-Q |
|||
60 IF R<0 THEN LET R=-R |
|||
70 IF Q>R THEN GOTO 130 |
|||
80 LET R = R - Q |
|||
90 IF Q=0 THEN GOTO 110 |
|||
100 GOTO 50 |
|||
110 LET U = (A*B)/R |
|||
111 IF U < 0 THEN LET U = - U |
|||
112 PRINT U |
|||
120 END |
|||
130 LET C=Q |
|||
140 LET Q=R |
|||
150 LET R=C |
|||
160 GOTO 70</syntaxhighlight> |
|||
=={{header|BASIC256}}== |
|||
===Iterative solution=== |
|||
<syntaxhighlight lang="basic256">function mcm (m, n) |
|||
if m = 0 or n = 0 then return 0 |
|||
if m < n then |
|||
t = m : m = n : n = t |
|||
end if |
|||
cont = 0 |
|||
do |
|||
cont += 1 |
|||
until (m * cont) mod n = 0 |
|||
return m * cont |
|||
end function |
|||
print "lcm( 12, 18) = "; mcm( 12, -18) |
|||
print "lcm( 15, 12) = "; mcm( 15, 12) |
|||
print "lcm(-10, -14) = "; mcm(-10, -14) |
|||
print "lcm( 0, 1) = "; mcm( 0, 1)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>lcm( 12, 18) = 36 |
|||
lcm( 15, 12) = 60 |
|||
lcm(-10, -14) = -70 |
|||
lcm( 0, 1) = 0</pre> |
|||
===Recursive solution=== |
|||
Reuses code from Greatest_common_divisor#Recursive_solution and correctly handles negative arguments |
|||
<syntaxhighlight lang="basic256">function gcdp(a, b) |
|||
if b = 0 then return a |
|||
return gcdp(b, a mod b) |
|||
end function |
|||
function gcd(a, b) |
|||
return gcdp(abs(a), abs(b)) |
|||
end function |
|||
function lcm(a, b) |
|||
return abs(a * b) / gcd(a, b) |
|||
end function |
|||
print "lcm( 12, -18) = "; lcm( 12, -18) |
|||
print "lcm( 15, 12) = "; lcm( 15, 12) |
|||
print "lcm(-10, -14) = "; lcm(-10, -14) |
|||
print "lcm( 0, 1) = "; lcm( 0, 1)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>lcm( 12, -18) = 36.0 |
|||
lcm( 15, 12) = 60.0 |
|||
lcm(-10, -14) = 70.0 |
|||
lcm( 0, 1) = 0.0</pre> |
|||
=={{header|Batch File}}== |
=={{header|Batch File}}== |
||
< |
<syntaxhighlight lang="dos">@echo off |
||
setlocal enabledelayedexpansion |
setlocal enabledelayedexpansion |
||
set num1=12 |
set num1=12 |
||
Line 440: | Line 752: | ||
set /a res = %1 %% %2 |
set /a res = %1 %% %2 |
||
call :lcm %2 %res% |
call :lcm %2 %res% |
||
goto :EOF</ |
goto :EOF</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>LCM = 36</pre> |
<pre>LCM = 36</pre> |
||
Line 446: | Line 758: | ||
=={{header|bc}}== |
=={{header|bc}}== |
||
{{trans|AWK}} |
{{trans|AWK}} |
||
< |
<syntaxhighlight lang="bc">/* greatest common divisor */ |
||
define g(m, n) { |
define g(m, n) { |
||
auto t |
auto t |
||
Line 467: | Line 779: | ||
if (r < 0) return (-r) |
if (r < 0) return (-r) |
||
return (r) |
return (r) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|BCPL}}== |
|||
<syntaxhighlight lang="bcpl">get "libhdr" |
|||
let lcm(m,n) = |
|||
m=0 -> 0, |
|||
n=0 -> 0, |
|||
abs(m*n) / gcd(m,n) |
|||
and gcd(m,n) = |
|||
n=0 -> m, |
|||
gcd(n, m rem n) |
|||
let start() be writef("%N*N", lcm(12, 18))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>36</pre> |
|||
=={{header|Befunge}}== |
|||
Inputs are limited to signed 16-bit integers. |
|||
<syntaxhighlight lang="befunge">&>:0`2*1-*:&>:#@!#._:0`2*1v |
|||
>28*:*:**+:28*>:*:*/\:vv*-< |
|||
|<:%/*:*:*82\%*:*:*82<<>28v |
|||
>$/28*:*:*/*.@^82::+**:*:*<</syntaxhighlight> |
|||
{{in}} |
|||
<pre>12345 |
|||
-23044</pre> |
|||
{{out}} |
|||
<pre>345660</pre> |
|||
=={{header|BQN}}== |
|||
<syntaxhighlight lang="bqn">Lcm ← ×÷{𝕨(|𝕊⍟(>⟜0)⊣)𝕩}</syntaxhighlight> |
|||
Example: |
|||
<syntaxhighlight lang="bqn">12 Lcm 18</syntaxhighlight> |
|||
<pre>36</pre> |
|||
=={{header|Bracmat}}== |
=={{header|Bracmat}}== |
||
We utilize the fact that Bracmat simplifies fractions (using Euclid's algorithm). The function <code>den$<i>number</i></code> returns the denominator of a number. |
We utilize the fact that Bracmat simplifies fractions (using Euclid's algorithm). The function <code>den$<i>number</i></code> returns the denominator of a number. |
||
< |
<syntaxhighlight lang="bracmat">(gcd= |
||
a b |
a b |
||
. !arg:(?a.?b) |
. !arg:(?a.?b) |
||
Line 478: | Line 829: | ||
* !a |
* !a |
||
); |
); |
||
out$(gcd$(12.18) gcd$(-6.14) gcd$(35.0) gcd$(117.18))</ |
out$(gcd$(12.18) gcd$(-6.14) gcd$(35.0) gcd$(117.18))</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>36 42 35 234</pre> |
<pre>36 42 35 234</pre> |
||
=={{header|Brat}}== |
=={{header|Brat}}== |
||
< |
<syntaxhighlight lang="brat"> |
||
gcd = { a, b | |
gcd = { a, b | |
||
true? { a == 0 } |
true? { a == 0 } |
||
Line 496: | Line 847: | ||
p lcm(12, 18) # 36 |
p lcm(12, 18) # 36 |
||
p lcm(14, 21) # 42 |
p lcm(14, 21) # 42 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Bruijn}}== |
|||
{{trans|Haskell}} |
|||
<syntaxhighlight lang="bruijn"> |
|||
:import std/Math . |
|||
lcm [[=?1 1 (=?0 0 |(1 / (gcd 1 0) ⋅ 0))]] |
|||
:test ((lcm (+12) (+18)) =? (+36)) ([[1]]) |
|||
:test ((lcm (+42) (+25)) =? (+1050)) ([[1]]) |
|||
</syntaxhighlight> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
int gcd(int m, int n) |
int gcd(int m, int n) |
||
Line 517: | Line 879: | ||
printf("lcm(35, 21) = %d\n", lcm(21,35)); |
printf("lcm(35, 21) = %d\n", lcm(21,35)); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C sharp|C#}}== |
|||
<syntaxhighlight lang="csharp">Using System; |
|||
class Program |
|||
{ |
|||
static int gcd(int m, int n) |
|||
{ |
|||
return n == 0 ? Math.Abs(m) : gcd(n, n % m); |
|||
} |
|||
static int lcm(int m, int n) |
|||
{ |
|||
return Math.Abs(m * n) / gcd(m, n); |
|||
} |
|||
static void Main() |
|||
{ |
|||
Console.WriteLine("lcm(12,18)=" + lcm(12,18)); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>lcm(12,18)=36</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{libheader|Boost}} |
{{libheader|Boost}} |
||
< |
<syntaxhighlight lang="cpp">#include <boost/math/common_factor.hpp> |
||
#include <iostream> |
#include <iostream> |
||
Line 529: | Line 912: | ||
<< "and the greatest common divisor " << boost::math::gcd( 12 , 18 ) << " !" << std::endl ; |
<< "and the greatest common divisor " << boost::math::gcd( 12 , 18 ) << " !" << std::endl ; |
||
return 0 ; |
return 0 ; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 538: | Line 921: | ||
=== Alternate solution === |
=== Alternate solution === |
||
{{works with|C++11}} |
{{works with|C++11}} |
||
< |
<syntaxhighlight lang="cpp"> |
||
#include <cstdlib> |
#include <cstdlib> |
||
#include <iostream> |
#include <iostream> |
||
#include <tuple> |
#include <tuple> |
||
using namespace std; |
|||
int gcd(int a, int b) { |
int gcd(int a, int b) { |
||
a = abs(a); |
a = abs(a); |
||
b = abs(b); |
b = abs(b); |
||
while (b != 0) { |
while (b != 0) { |
||
tie(a, b) = make_tuple(b, a % b); |
std::tie(a, b) = std::make_tuple(b, a % b); |
||
} |
} |
||
return a; |
return a; |
||
} |
} |
||
int lcm(int a, int b) { |
int lcm(int a, int b) { |
||
int c = gcd(a, b); |
int c = gcd(a, b); |
||
return c == 0 ? 0 : a / c * b; |
return c == 0 ? 0 : a / c * b; |
||
} |
} |
||
int main() { |
int main() { |
||
cout << "The least common multiple of 12 and 18 is " << lcm(12, 18) |
std::cout << "The least common multiple of 12 and 18 is " << lcm(12, 18) << ",\n" |
||
<< "and their greatest common divisor is " << gcd(12, 18) << "!" |
|||
<< std::endl; |
|||
<< "and the greatest common divisor " << gcd(12, 18) << " !" << endl; |
|||
return 0; |
return 0; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|C sharp|C#}}== |
|||
<lang csharp>Using System; |
|||
class Program |
|||
{ |
|||
static int gcd(int m, int n) |
|||
{ |
|||
return n == 0 ? Math.Abs(m) : gcd(n, n % m); |
|||
} |
|||
static int lcm(int m, int n) |
|||
{ |
|||
return Math.Abs(m * n) / gcd(m, n); |
|||
} |
|||
static void Main() |
|||
{ |
|||
Console.WriteLine("lcm(12,18)=" + lcm(12,18)); |
|||
} |
|||
} |
|||
</lang> |
|||
{{out}} |
|||
<pre>lcm(12,18)=36</pre> |
|||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
< |
<syntaxhighlight lang="clojure">(defn gcd |
||
[a b] |
[a b] |
||
(if (zero? b) |
(if (zero? b) |
||
Line 600: | Line 960: | ||
;; to calculate the lcm for a variable number of arguments |
;; to calculate the lcm for a variable number of arguments |
||
(defn lcmv [& v] (reduce lcm v)) |
(defn lcmv [& v] (reduce lcm v)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|CLU}}== |
|||
<syntaxhighlight lang="clu">gcd = proc (m, n: int) returns (int) |
|||
m, n := int$abs(m), int$abs(n) |
|||
while n ~= 0 do m, n := n, m // n end |
|||
return(m) |
|||
end gcd |
|||
lcm = proc (m, n: int) returns (int) |
|||
if m=0 cor n=0 |
|||
then return(0) |
|||
else return(int$abs(m*n) / gcd(m,n)) |
|||
end |
|||
end lcm |
|||
start_up = proc () |
|||
po: stream := stream$primary_output() |
|||
stream$putl(po, int$unparse(lcm(12, 18))) |
|||
end start_up</syntaxhighlight> |
|||
{{out}} |
|||
<pre>36</pre> |
|||
=={{header|COBOL}}== |
=={{header|COBOL}}== |
||
< |
<syntaxhighlight lang="cobol"> IDENTIFICATION DIVISION. |
||
PROGRAM-ID. show-lcm. |
PROGRAM-ID. show-lcm. |
||
Line 665: | Line 1,046: | ||
GOBACK |
GOBACK |
||
. |
. |
||
END FUNCTION gcd.</ |
END FUNCTION gcd.</syntaxhighlight> |
||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
Common Lisp provides the <tt>lcm</tt> function. It can accept two or more (or less) parameters. |
Common Lisp provides the <tt>lcm</tt> function. It can accept two or more (or less) parameters. |
||
< |
<syntaxhighlight lang="lisp">CL-USER> (lcm 12 18) |
||
36 |
36 |
||
CL-USER> (lcm 12 18 22) |
CL-USER> (lcm 12 18 22) |
||
396</ |
396</syntaxhighlight> |
||
Here is one way to reimplement it. |
Here is one way to reimplement it. |
||
< |
<syntaxhighlight lang="lisp">CL-USER> (defun my-lcm (&rest args) |
||
(reduce (lambda (m n) |
(reduce (lambda (m n) |
||
(cond ((or (= m 0) (= n 0)) 0) |
(cond ((or (= m 0) (= n 0)) 0) |
||
Line 686: | Line 1,067: | ||
36 |
36 |
||
CL-USER> (my-lcm 12 18 22) |
CL-USER> (my-lcm 12 18 22) |
||
396</ |
396</syntaxhighlight> |
||
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>. |
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|Cowgol}}== |
|||
<syntaxhighlight lang="cowgol">include "cowgol.coh"; |
|||
sub gcd(m: uint32, n: uint32): (r: uint32) is |
|||
while n != 0 loop |
|||
var t := m; |
|||
m := n; |
|||
n := t % n; |
|||
end loop; |
|||
r := m; |
|||
end sub; |
|||
sub lcm(m: uint32, n: uint32): (r: uint32) is |
|||
if m==0 or n==0 then |
|||
r := 0; |
|||
else |
|||
r := m*n / gcd(m,n); |
|||
end if; |
|||
end sub; |
|||
print_i32(lcm(12, 18)); |
|||
print_nl();</syntaxhighlight> |
|||
{{out}} |
|||
<pre>36</pre> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
< |
<syntaxhighlight lang="d">import std.stdio, std.bigint, std.math; |
||
T gcd(T)(T a, T b) pure nothrow { |
T gcd(T)(T a, T b) pure nothrow { |
||
Line 712: | Line 1,118: | ||
lcm("2562047788015215500854906332309589561".BigInt, |
lcm("2562047788015215500854906332309589561".BigInt, |
||
"6795454494268282920431565661684282819".BigInt).writeln; |
"6795454494268282920431565661684282819".BigInt).writeln; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>36 |
<pre>36 |
||
15669251240038298262232125175172002594731206081193527869</pre> |
15669251240038298262232125175172002594731206081193527869</pre> |
||
=={{header|DWScript}}== |
|||
<lang delphi>PrintLn(Lcm(12, 18));</lang> |
|||
Output: |
|||
<pre>36</pre> |
|||
=={{header|Dart}}== |
=={{header|Dart}}== |
||
< |
<syntaxhighlight lang="dart"> |
||
main() { |
main() { |
||
int x=8; |
int x=8; |
||
Line 739: | Line 1,141: | ||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Delphi}}== |
|||
See [https://rosettacode.org/wiki/Least_common_multiple#Pascal Pascal]. |
|||
=={{header|DWScript}}== |
|||
<syntaxhighlight lang="delphi">PrintLn(Lcm(12, 18));</syntaxhighlight> |
|||
Output: |
|||
<pre>36</pre> |
|||
=={{header|Draco}}== |
|||
<syntaxhighlight lang="draco">proc gcd(word m, n) word: |
|||
word t; |
|||
while n /= 0 do |
|||
t := m; |
|||
m := n; |
|||
n := t % n |
|||
od; |
|||
m |
|||
corp |
|||
proc lcm(word m, n) word: |
|||
if m=0 or n=0 |
|||
then 0 |
|||
else m*n / gcd(m,n) |
|||
fi |
|||
corp |
|||
proc main() void: |
|||
writeln(lcm(12, 18)) |
|||
corp</syntaxhighlight> |
|||
{{out}} |
|||
<pre>36</pre> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight> |
|||
func gcd a b . |
|||
while b <> 0 |
|||
h = b |
|||
b = a mod b |
|||
a = h |
|||
. |
|||
return a |
|||
. |
|||
func lcm a b . |
|||
return a / gcd a b * b |
|||
. |
|||
print lcm 12 18 |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
36 |
|||
</pre> |
|||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
(lcm a b) is already here as a two arguments function. Use foldl to find the lcm of a list of numbers. |
(lcm a b) is already here as a two arguments function. Use foldl to find the lcm of a list of numbers. |
||
< |
<syntaxhighlight lang="lisp"> |
||
(lcm 0 9) → 0 |
(lcm 0 9) → 0 |
||
(lcm 444 888)→ 888 |
(lcm 444 888)→ 888 |
||
Line 749: | Line 1,203: | ||
(define (lcm* list) (foldl lcm (first list) list)) → lcm* |
(define (lcm* list) (foldl lcm (first list) list)) → lcm* |
||
(lcm* '(444 888 999)) → 7992 |
(lcm* '(444 888 999)) → 7992 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Elena}}== |
|||
{{trans|C#}} |
|||
ELENA 6.x : |
|||
<syntaxhighlight lang="elena">import extensions; |
|||
import system'math; |
|||
gcd = (m,n => (n == 0) ? (m.Absolute) : (gcd(n,n.mod(m)))); |
|||
lcm = (m,n => (m * n).Absolute / gcd(m,n)); |
|||
public program() |
|||
{ |
|||
console.printLine("lcm(12,18)=",lcm(12,18)) |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
lcm(12,18)=36 |
|||
</pre> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
< |
<syntaxhighlight lang="elixir">defmodule RC do |
||
def gcd(a,0), do: abs(a) |
def gcd(a,0), do: abs(a) |
||
def gcd(a,b), do: gcd(b, rem(a,b)) |
def gcd(a,b), do: gcd(b, rem(a,b)) |
||
Line 760: | Line 1,232: | ||
end |
end |
||
IO.puts RC.lcm(-12,15)</ |
IO.puts RC.lcm(-12,15)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 768: | Line 1,240: | ||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
< |
<syntaxhighlight lang="erlang">% Implemented by Arjun Sunel |
||
-module(lcm). |
-module(lcm). |
||
-export([main/0]). |
-export([main/0]). |
||
Line 782: | Line 1,254: | ||
lcm(A,B) -> |
lcm(A,B) -> |
||
abs(A*B div gcd(A,B)).</ |
abs(A*B div gcd(A,B)).</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 789: | Line 1,261: | ||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
< |
<syntaxhighlight lang="erre">PROGRAM LCM |
||
PROCEDURE GCD(A,B->GCD) |
PROCEDURE GCD(A,B->GCD) |
||
Line 818: | Line 1,290: | ||
LCM(0,35->LCM) |
LCM(0,35->LCM) |
||
PRINT("LCM of 0 AND 35 =";LCM) |
PRINT("LCM of 0 AND 35 =";LCM) |
||
END PROGRAM</ |
END PROGRAM</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 825: | Line 1,297: | ||
LCM of 0 and 35 = 0 |
LCM of 0 and 35 = 0 |
||
</pre> |
</pre> |
||
=={{header|Euler}}== |
|||
Note % is integer division in Euler, not the mod operator. |
|||
'''begin''' |
|||
'''new''' gcd; '''new''' lcm; |
|||
gcd <- ` '''formal''' a; '''formal''' b; |
|||
'''if''' b = 0 '''then''' a '''else''' gcd( b, a '''mod''' '''abs''' b ) |
|||
' |
|||
; |
|||
lcm <- ` '''formal''' a; '''formal''' b; |
|||
'''abs''' [ a * b ] % gcd( a, b ) |
|||
' |
|||
; |
|||
'''out''' lcm( 15, 20 ) |
|||
'''end''' $ |
|||
=={{header|Euphoria}}== |
=={{header|Euphoria}}== |
||
< |
<syntaxhighlight lang="euphoria">function gcd(integer m, integer n) |
||
integer tmp |
integer tmp |
||
while m do |
while m do |
||
Line 839: | Line 1,328: | ||
function lcm(integer m, integer n) |
function lcm(integer m, integer n) |
||
return m / gcd(m, n) * n |
return m / gcd(m, n) * n |
||
end function</ |
end function</syntaxhighlight> |
||
=={{header|Excel}}== |
=={{header|Excel}}== |
||
Excel's LCM can handle multiple values. Type in a cell: |
Excel's LCM can handle multiple values. Type in a cell: |
||
< |
<syntaxhighlight lang="excel">=LCM(A1:J1)</syntaxhighlight> |
||
This will get the LCM on the first 10 cells in the first row. Thus : |
This will get the LCM on the first 10 cells in the first row. Thus : |
||
<pre>12 3 5 23 13 67 15 9 4 2 |
<pre>12 3 5 23 13 67 15 9 4 2 |
||
Line 850: | Line 1,339: | ||
=={{header|Ezhil}}== |
=={{header|Ezhil}}== |
||
< |
<syntaxhighlight lang="src="ezhil""> |
||
## இந்த நிரல் இரு எண்களுக்கு இடையிலான மீச்சிறு பொது மடங்கு (LCM), மீப்பெரு பொது வகுத்தி (GCD) என்ன என்று கணக்கிடும் |
## இந்த நிரல் இரு எண்களுக்கு இடையிலான மீச்சிறு பொது மடங்கு (LCM), மீப்பெரு பொது வகுத்தி (GCD) என்ன என்று கணக்கிடும் |
||
Line 907: | Line 1,396: | ||
பதிப்பி "நீங்கள் தந்த இரு எண்களின் மீபொம (மீச்சிறு பொது மடங்கு, LCM) = ", மீபொம(அ, ஆ) |
பதிப்பி "நீங்கள் தந்த இரு எண்களின் மீபொம (மீச்சிறு பொது மடங்கு, LCM) = ", மீபொம(அ, ஆ) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight 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)</ |
let lcm x y = x * y / (gcd x y)</syntaxhighlight> |
||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
The vocabulary ''math.functions'' already provides ''lcm''. |
The vocabulary ''math.functions'' already provides ''lcm''. |
||
< |
<syntaxhighlight lang="factor">USING: math.functions prettyprint ; |
||
26 28 lcm .</ |
26 28 lcm .</syntaxhighlight> |
||
This program outputs ''364''. |
This program outputs ''364''. |
||
Line 925: | Line 1,413: | ||
One can also reimplement ''lcm''. |
One can also reimplement ''lcm''. |
||
< |
<syntaxhighlight lang="factor">USING: kernel math prettyprint ; |
||
IN: script |
IN: script |
||
Line 936: | Line 1,424: | ||
[ * abs ] [ gcd ] 2bi / ; |
[ * abs ] [ gcd ] 2bi / ; |
||
26 28 lcm .</ |
26 28 lcm .</syntaxhighlight> |
||
=={{header|Fermat}}== |
|||
<syntaxhighlight lang="fermat">Func Lecm(a,b)=|a|*|b|/GCD(a,b).</syntaxhighlight> |
|||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
< |
<syntaxhighlight lang="forth">: gcd ( a b -- n ) |
||
begin dup while tuck mod repeat drop ; |
begin dup while tuck mod repeat drop ; |
||
: lcm ( a b -- n ) |
: lcm ( a b -- n ) |
||
over 0= over 0= or if 2drop 0 exit then |
over 0= over 0= or if 2drop 0 exit then |
||
2dup gcd abs */ ;</ |
2dup gcd abs */ ;</syntaxhighlight> |
||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
This solution is written as a combination of 2 functions, but a subroutine implementation would work great as well. |
This solution is written as a combination of 2 functions, but a subroutine implementation would work great as well. |
||
<syntaxhighlight lang="fortran"> |
|||
<lang Fortran> |
|||
integer function lcm(a,b) |
integer function lcm(a,b) |
||
integer:: a,b |
integer:: a,b |
||
Line 963: | Line 1,454: | ||
gcd = abs(a) |
gcd = abs(a) |
||
end function gcd |
end function gcd |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
===Iterative solution=== |
|||
<lang freebasic>' FB 1.05.0 Win64 |
|||
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 |
|||
Function lcm (m As Integer, n As Integer) As Integer |
Function lcm (m As Integer, n As Integer) As Integer |
||
Line 982: | Line 1,475: | ||
Print |
Print |
||
Print "Press any key to quit" |
Print "Press any key to quit" |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 989: | Line 1,482: | ||
lcm(15, 12) = 60 |
lcm(15, 12) = 60 |
||
lcm(10, 14) = 70 |
lcm(10, 14) = 70 |
||
</pre> |
|||
===Recursive solution=== |
|||
Reuses code from [[Greatest_common_divisor#Recursive_solution]] and correctly handles negative arguments |
|||
<syntaxhighlight lang="freebasic">function gcdp( a as uinteger, b as uinteger ) as uinteger |
|||
if b = 0 then return a |
|||
return gcdp( b, a mod b ) |
|||
end function |
|||
function gcd(a as integer, b as integer) as uinteger |
|||
return gcdp( abs(a), abs(b) ) |
|||
end function |
|||
function lcm(a as integer, b as integer) as uinteger |
|||
return abs(a*b)/gcd(a,b) |
|||
end function |
|||
print "lcm( 12, -18) = "; lcm(12, -18) |
|||
print "lcm( 15, 12) = "; lcm(15, 12) |
|||
print "lcm(-10, -14) = "; lcm(-10, -14) |
|||
print "lcm( 0, 1) = "; lcm(0,1)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
lcm( 12, -18) = 36 |
|||
lcm( 15, 12) = 60 |
|||
lcm(-10, -14) = 70 |
|||
lcm( 0, 1) = 0 |
|||
</pre> |
</pre> |
||
=={{header|Frink}}== |
=={{header|Frink}}== |
||
Frink has a built-in LCM function that handles arbitrarily-large integers. |
Frink has a built-in LCM function that handles arbitrarily-large integers. |
||
< |
<syntaxhighlight lang="frink"> |
||
println[lcm[2562047788015215500854906332309589561, 6795454494268282920431565661684282819]] |
println[lcm[2562047788015215500854906332309589561, 6795454494268282920431565661684282819]] |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|FunL}}== |
=={{header|FunL}}== |
||
FunL has function <code>lcm</code> in module <code>integers</code> with the following definition: |
FunL has function <code>lcm</code> in module <code>integers</code> with the following definition: |
||
< |
<syntaxhighlight lang="funl">def |
||
lcm( _, 0 ) = 0 |
lcm( _, 0 ) = 0 |
||
lcm( 0, _ ) = 0 |
lcm( 0, _ ) = 0 |
||
lcm( x, y ) = abs( (x\gcd(x, y)) y )</ |
lcm( x, y ) = abs( (x\gcd(x, y)) y )</syntaxhighlight> |
||
=={{header|GAP}}== |
=={{header|GAP}}== |
||
< |
<syntaxhighlight lang="gap"># Built-in |
||
LcmInt(12, 18); |
LcmInt(12, 18); |
||
# 36</ |
# 36</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 1,027: | Line 1,548: | ||
func main() { |
func main() { |
||
fmt.Println(z.Mul(z.Div(&m, z.GCD(nil, nil, &m, &n)), &n)) |
fmt.Println(z.Mul(z.Div(&m, z.GCD(nil, nil, &m, &n)), &n)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,034: | Line 1,555: | ||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
< |
<syntaxhighlight lang="groovy">def gcd |
||
gcd = { m, n -> m = m.abs(); n = n.abs(); n == 0 ? m : m%n == 0 ? n : gcd(n, m % n) } |
gcd = { m, n -> m = m.abs(); n = n.abs(); n == 0 ? m : m%n == 0 ? n : gcd(n, m % n) } |
||
Line 1,044: | Line 1,565: | ||
println "LCD of $t.m, $t.n is $t.l" |
println "LCD of $t.m, $t.n is $t.l" |
||
assert lcd(t.m, t.n) == t.l |
assert lcd(t.m, t.n) == t.l |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>LCD of 12, 18 is 36 |
<pre>LCD of 12, 18 is 36 |
||
LCD of -6, 14 is 42 |
LCD of -6, 14 is 42 |
||
LCD of 35, 0 is 0</pre> |
LCD of 35, 0 is 0</pre> |
||
=={{header|GW-BASIC}}== |
|||
{{trans|C}} |
|||
{{works with|PC-BASIC|any}} |
|||
<syntaxhighlight lang="qbasic"> |
|||
10 PRINT "LCM(35, 21) = "; |
|||
20 LET MLCM = 35 |
|||
30 LET NLCM = 21 |
|||
40 GOSUB 200: ' Calculate LCM |
|||
50 PRINT LCM |
|||
60 END |
|||
195 ' Calculate LCM |
|||
200 LET MGCD = MLCM |
|||
210 LET NGCD = NLCM |
|||
220 GOSUB 400: ' Calculate GCD |
|||
230 LET LCM = MLCM / GCD * NLCM |
|||
240 RETURN |
|||
395 ' Calculate GCD |
|||
400 WHILE MGCD <> 0 |
|||
410 LET TMP = MGCD |
|||
420 LET MGCD = NGCD MOD MGCD |
|||
430 LET NGCD = TMP |
|||
440 WEND |
|||
450 LET GCD = NGCD |
|||
460 RETURN |
|||
</syntaxhighlight> |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Line 1,054: | Line 1,603: | ||
That is already available as the function ''lcm'' in the Prelude. Here's the implementation: |
That is already available as the function ''lcm'' in the Prelude. Here's the implementation: |
||
< |
<syntaxhighlight lang="haskell">lcm :: (Integral a) => a -> a -> a |
||
lcm _ 0 = 0 |
lcm _ 0 = 0 |
||
lcm 0 _ = 0 |
lcm 0 _ = 0 |
||
lcm x y = abs ((x `quot` (gcd x y)) * y)</ |
lcm x y = abs ((x `quot` (gcd x y)) * y)</syntaxhighlight> |
||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
The lcm routine from the Icon Programming Library uses gcd. The routine is |
The lcm routine from the Icon Programming Library uses gcd. The routine is |
||
< |
<syntaxhighlight lang="icon">link numbers |
||
procedure main() |
procedure main() |
||
write("lcm of 18, 36 = ",lcm(18,36)) |
write("lcm of 18, 36 = ",lcm(18,36)) |
||
write("lcm of 0, 9 |
write("lcm of 0, 9 = ",lcm(0,9)) |
||
end</ |
end</syntaxhighlight> |
||
{{libheader|Icon Programming Library}} |
{{libheader|Icon Programming Library}} |
||
[http://www.cs.arizona.edu/icon/library/src/procs/numbers.icn numbers provides lcm and gcd] and looks like this: |
[http://www.cs.arizona.edu/icon/library/src/procs/numbers.icn numbers provides lcm and gcd] and looks like this: |
||
< |
<syntaxhighlight lang="icon">procedure lcm(i, j) #: least common multiple |
||
if (i = 0) | (j = 0) then return 0 |
if (i = 0) | (j = 0) then return 0 |
||
return abs(i * j) / gcd(i, j) |
return abs(i * j) / gcd(i, j) |
||
end</ |
end</syntaxhighlight> |
||
=={{header|J}}== |
=={{header|J}}== |
||
J provides the dyadic verb <code>*.</code> which returns the least common multiple of its left and right arguments. |
J provides the dyadic verb <code>*.</code> which returns the least common multiple of its left and right arguments. |
||
< |
<syntaxhighlight lang="j"> 12 *. 18 |
||
36 |
36 |
||
12 *. 18 22 |
12 *. 18 22 |
||
Line 1,088: | Line 1,637: | ||
*./~ 0 1 |
*./~ 0 1 |
||
0 0 |
0 0 |
||
0 1</ |
0 1</syntaxhighlight> |
||
Note: least common multiple is the original boolean multiplication. Constraining the universe of values to 0 and 1 allows us to additionally define logical negation (and boolean algebra was redefined to include this constraint in the early 1900s - the original concept of boolean algebra is now known as a boolean ring). |
Note: least common multiple is the original boolean multiplication. Constraining the universe of values to 0 and 1 allows us to additionally define logical negation (and boolean algebra was redefined to include this constraint in the early 1900s - the original concept of boolean algebra is now known as a boolean ring (though, talking to some people: there's been some linguistic drift even there)). |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java">import java.util.Scanner; |
||
public class LCM{ |
public class LCM{ |
||
Line 1,119: | Line 1,668: | ||
System.out.println("lcm(" + m + ", " + n + ") = " + lcm); |
System.out.println("lcm(" + m + ", " + n + ") = " + lcm); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
Line 1,130: | Line 1,679: | ||
<math>\operatorname{lcm}(a_1,a_2,\ldots,a_n) = \operatorname{lcm}(\operatorname{lcm}(a_1,a_2,\ldots,a_{n-1}),a_n).</math> |
<math>\operatorname{lcm}(a_1,a_2,\ldots,a_n) = \operatorname{lcm}(\operatorname{lcm}(a_1,a_2,\ldots,a_{n-1}),a_n).</math> |
||
< |
<syntaxhighlight lang="javascript">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]); |
var n = A.length, a = Math.abs(A[0]); |
||
Line 1,143: | Line 1,692: | ||
/* For example: |
/* For example: |
||
LCM([-50,25,-45,-18,90,447]) -> 67050 |
LCM([-50,25,-45,-18,90,447]) -> 67050 |
||
*/</ |
*/</syntaxhighlight> |
||
===ES6=== |
===ES6=== |
||
{{Trans|Haskell}} |
{{Trans|Haskell}} |
||
< |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 1,165: | Line 1,714: | ||
return lcm(12, 18); |
return lcm(12, 18); |
||
})();</ |
})();</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
Line 1,172: | Line 1,721: | ||
=={{header|jq}}== |
=={{header|jq}}== |
||
Direct method |
Direct method |
||
< |
<syntaxhighlight lang="jq"># Define the helper function to take advantage of jq's tail-recursion optimization |
||
def lcm(m; n): |
def lcm(m; n): |
||
def _lcm: |
def _lcm: |
||
# state is [m, n, i] |
# state is [m, n, i] |
||
if (.[2] % .[1]) == 0 then .[2] else (.[0:2] + [.[2] + m]) | _lcm end; |
if (.[2] % .[1]) == 0 then .[2] else (.[0:2] + [.[2] + m]) | _lcm end; |
||
[m, n, m] | _lcm; </ |
[m, n, m] | _lcm; </syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Built-in function: |
Built-in function: |
||
<lang |
<syntaxhighlight lang="julia">lcm(m,n)</syntaxhighlight> |
||
=={{header|K}}== |
=={{header|K}}== |
||
===K3=== |
|||
<lang K> gcd:{:[~x;y;_f[y;x!y]]} |
|||
{{works with|Kona}} |
|||
<syntaxhighlight lang="k"> gcd:{:[~x;y;_f[y;x!y]]} |
|||
lcm:{_abs _ x*y%gcd[x;y]} |
lcm:{_abs _ x*y%gcd[x;y]} |
||
lcm .'(12 18; -6 14; 35 0) |
lcm .'(12 18; -6 14; 35 0) |
||
36 42 0 |
36 42 0 |
||
lcm/1+!20 |
|||
232792560</syntaxhighlight> |
|||
===K6=== |
|||
{{works with|ngn/k}} |
|||
<syntaxhighlight lang="k"> abs:|/-:\ |
|||
gcd:{$[~x;y;o[x!y;x]]} |
|||
lcm:{abs[`i$x*y%gcd[x;y]]} |
|||
lcm .'(12 18; -6 14; 35 0) |
|||
36 42 0 |
|||
lcm/1+!20 |
lcm/1+!20 |
||
232792560</ |
232792560</syntaxhighlight> |
||
=={{header|Klingphix}}== |
|||
<syntaxhighlight lang="klingphix">:gcd { u v -- n } |
|||
abs int swap abs int swap |
|||
[over over mod rot drop] |
|||
[dup] |
|||
while |
|||
drop |
|||
; |
|||
:lcm { m n -- n } |
|||
over over gcd rot swap div mult |
|||
; |
|||
12 18 lcm print nl { 36 } |
|||
"End " input</syntaxhighlight> |
|||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">fun main(args: Array<String>) { |
||
fun gcd(a: |
fun gcd(a: Long, b: Long): Long = if (b == 0L) a else gcd(b, a % b) |
||
fun lcm(a: |
fun lcm(a: Long, b: Long): Long = a / gcd(a, b) * b |
||
println(lcm(15, 9)) |
println(lcm(15, 9)) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|LabVIEW}}== |
=={{header|LabVIEW}}== |
||
Requires [[Greatest common divisor#LabVIEW|GCD]]. {{VI solution|LabVIEW_Least_common_multiple.png}} |
Requires [[Greatest common divisor#LabVIEW|GCD]]. {{VI solution|LabVIEW_Least_common_multiple.png}} |
||
=={{header|Lasso}}== |
=={{header|Lasso}}== |
||
< |
<syntaxhighlight lang="lasso">define gcd(a,b) => { |
||
while(#b != 0) => { |
while(#b != 0) => { |
||
local(t = #b) |
local(t = #b) |
||
Line 1,224: | Line 1,801: | ||
lcm(12, 18) |
lcm(12, 18) |
||
lcm(12, 22) |
lcm(12, 22) |
||
lcm(7, 31)</ |
lcm(7, 31)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>42 |
<pre>42 |
||
Line 1,233: | Line 1,810: | ||
=={{header|Liberty BASIC}}== |
=={{header|Liberty BASIC}}== |
||
< |
<syntaxhighlight lang="lb">print "Least Common Multiple of 12 and 18 is "; LCM(12, 18) |
||
end |
end |
||
function LCM(m,n) |
function LCM(m, n) |
||
LCM=abs(m*n)/GCD(m,n) |
LCM = abs(m * n) / GCD(m, n) |
||
end function |
|||
function GCD(a,b) |
function GCD(a, b) |
||
while b |
while b |
||
c = a |
c = a |
||
Line 1,247: | Line 1,824: | ||
wend |
wend |
||
GCD = abs(a) |
GCD = abs(a) |
||
end function |
|||
</ |
</syntaxhighlight> |
||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
< |
<syntaxhighlight lang="logo">to abs :n |
||
output sqrt product :n :n |
output sqrt product :n :n |
||
end |
end |
||
Line 1,261: | Line 1,838: | ||
to lcm :m :n |
to lcm :m :n |
||
output quotient (abs product :m :n) gcd :m :n |
output quotient (abs product :m :n) gcd :m :n |
||
end</ |
end</syntaxhighlight> |
||
Demo code: |
Demo code: |
||
<lang |
<syntaxhighlight lang="logo">print lcm 38 46</syntaxhighlight> |
||
Output: |
Output: |
||
Line 1,272: | Line 1,849: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">function gcd( m, n ) |
||
while n ~= 0 do |
while n ~= 0 do |
||
local q = m |
local q = m |
||
Line 1,285: | Line 1,862: | ||
end |
end |
||
print( lcm(12,18) )</ |
print( lcm(12,18) )</syntaxhighlight> |
||
=={{header|m4}}== |
|||
This should work with any POSIX-compliant m4. I have tested it with OpenBSD m4, GNU m4, and Heirloom Devtools m4. |
|||
<syntaxhighlight lang="m4">divert(-1) |
|||
define(`gcd', |
|||
`ifelse(eval(`0 <= (' $1 `)'),`0',`gcd(eval(`-(' $1 `)'),eval(`(' $2 `)'))', |
|||
eval(`0 <= (' $2 `)'),`0',`gcd(eval(`(' $1 `)'),eval(`-(' $2 `)'))', |
|||
eval(`(' $1 `) == 0'),`0',`gcd(eval(`(' $2 `) % (' $1 `)'),eval(`(' $1 `)'))', |
|||
eval(`(' $2 `)'))') |
|||
define(`lcm', |
|||
`ifelse(eval(`0 <= (' $1 `)'),`0',`lcm(eval(`-(' $1 `)'),eval(`(' $2 `)'))', |
|||
eval(`0 <= (' $2 `)'),`0',`lcm(eval(`(' $1 `)'),eval(`-(' $2 `)'))', |
|||
eval(`(' $1 `) == 0'),`0',`eval(`(' $1 `) * (' $2 `) /' gcd(eval(`(' $1 `)'),eval(`(' $2 `)')))')') |
|||
divert`'dnl |
|||
dnl |
|||
lcm(-6, 14) = 42 |
|||
lcm(2, 0) = 0 |
|||
lcm(12, 18) = 36 |
|||
lcm(12, 22) = 132 |
|||
lcm(7, 31) = 217</syntaxhighlight> |
|||
{{out}} |
|||
<pre>42 = 42 |
|||
0 = 0 |
|||
36 = 36 |
|||
132 = 132 |
|||
217 = 217</pre> |
|||
=={{header|Maple}}== |
=={{header|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. |
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. |
||
< |
<syntaxhighlight lang="maple">> ilcm( 12, 18 ); |
||
36 |
36 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Mathematica}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">LCM[18,12] |
||
-> 36</ |
-> 36</syntaxhighlight> |
||
=={{header|MATLAB}} / {{header|Octave}}== |
=={{header|MATLAB}} / {{header|Octave}}== |
||
<lang |
<syntaxhighlight lang="matlab"> lcm(a,b) </syntaxhighlight> |
||
=={{header|Maxima}}== |
=={{header|Maxima}}== |
||
< |
<syntaxhighlight 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), |
/* 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 */ |
so the lcm may be negative. To get a positive lcm, simply do */ |
||
abs(lcm(a, b))</ |
abs(lcm(a, b))</syntaxhighlight> |
||
=={{header|Microsoft Small Basic}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="microsoftsmallbasic"> |
|||
Textwindow.Write("LCM(35, 21) = ") |
|||
mlcm = 35 |
|||
nlcm = 21 |
|||
CalculateLCM() |
|||
TextWindow.WriteLine(lcm) |
|||
Sub CalculateLCM |
|||
mgcd = mlcm |
|||
ngcd = nlcm |
|||
CalculateGCD() |
|||
lcm = mlcm / gcd * nlcm |
|||
EndSub |
|||
Sub CalculateGCD |
|||
While mgcd <> 0 |
|||
tmp = mgcd |
|||
mgcd = Math.Remainder(ngcd, mgcd) |
|||
ngcd = tmp |
|||
EndWhile |
|||
gcd = ngcd |
|||
EndSub |
|||
</syntaxhighlight> |
|||
=={{header|MiniScript}}== |
|||
<syntaxhighlight lang="miniscript">gcd = function(a, b) |
|||
while b |
|||
temp = b |
|||
b = a % b |
|||
a = temp |
|||
end while |
|||
return abs(a) |
|||
end function |
|||
lcm = function(a,b) |
|||
if not a and not b then return 0 |
|||
return abs(a * b) / gcd(a, b) |
|||
end function |
|||
print lcm(18,12) |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre>36</pre> |
|||
=={{header|MiniZinc}}== |
|||
<syntaxhighlight lang="minizinc">function var int: lcm(int: a2,int:b2) = |
|||
let { |
|||
int:a1 = max(a2,b2); |
|||
int:b1 = min(a2,b2); |
|||
array[0..a1,0..b1] of var int: gcd; |
|||
constraint forall(a in 0..a1)( |
|||
forall(b in 0..b1)( |
|||
gcd[a,b] == |
|||
if (b == 0) then |
|||
a |
|||
else |
|||
gcd[b, a mod b] |
|||
endif |
|||
) |
|||
) |
|||
} in (a1*b1) div gcd[a1,b1]; |
|||
var int: lcm1 = lcm(18,12); |
|||
solve satisfy; |
|||
output [show(lcm1),"\n"];</syntaxhighlight> |
|||
{{output}} |
|||
<pre>36</pre> |
|||
=={{header|min}}== |
|||
{{works with|min|0.19.6}} |
|||
<syntaxhighlight lang="min">((0 <) (-1 *) when) :abs |
|||
((dup 0 ==) (pop abs) (swap over mod) () linrec) :gcd |
|||
(over over gcd '* dip div) :lcm</syntaxhighlight> |
|||
=={{header|МК-61/52}}== |
=={{header|МК-61/52}}== |
||
<lang>ИПA ИПB * |x| ПC ИПA ИПB / [x] П9 |
<syntaxhighlight lang="text">ИПA ИПB * |x| ПC ИПA ИПB / [x] П9 |
||
ИПA ИПB ПA ИП9 * - ПB x=0 05 ИПC |
ИПA ИПB ПA ИП9 * - ПB x=0 05 ИПC |
||
ИПA / С/П</ |
ИПA / С/П</syntaxhighlight> |
||
=={{header|ML}}== |
=={{header|ML}}== |
||
==={{header|mLite}}=== |
==={{header|mLite}}=== |
||
< |
<syntaxhighlight lang="ocaml">fun gcd (a, 0) = a |
||
| (0, b) = b |
| (0, b) = b |
||
| (a, b) where (a < b) |
| (a, b) where (a < b) |
||
Line 1,325: | Line 2,007: | ||
in a * b div d |
in a * b div d |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Modula-2}}== |
|||
{{trans|C}} |
|||
{{works with|ADW Modula-2|any (Compile with the linker option ''Console Application'').}} |
|||
<syntaxhighlight lang="modula2"> |
|||
MODULE LeastCommonMultiple; |
|||
FROM STextIO IMPORT |
|||
WriteString, WriteLn; |
|||
FROM SWholeIO IMPORT |
|||
WriteInt; |
|||
PROCEDURE GCD(M, N: INTEGER): INTEGER; |
|||
VAR |
|||
Tmp: INTEGER; |
|||
BEGIN |
|||
WHILE M <> 0 DO |
|||
Tmp := M; |
|||
M := N MOD M; |
|||
N := Tmp; |
|||
END; |
|||
RETURN N; |
|||
END GCD; |
|||
PROCEDURE LCM(M, N: INTEGER): INTEGER; |
|||
BEGIN |
|||
RETURN M / GCD(M, N) * N; |
|||
END LCM; |
|||
BEGIN |
|||
WriteString("LCM(35, 21) = "); |
|||
WriteInt(LCM(35, 21), 1); |
|||
WriteLn; |
|||
END LeastCommonMultiple. |
|||
</syntaxhighlight> |
|||
=={{header|Nanoquery}}== |
|||
<syntaxhighlight lang="nanoquery">def gcd(a, b) |
|||
if (a < 1) or (b < 1) |
|||
throw new(InvalidNumberException, "gcd cannot be calculated on values < 1") |
|||
end |
|||
c = 0 |
|||
while b != 0 |
|||
c = a |
|||
a = b |
|||
b = c % b |
|||
end |
|||
return a |
|||
end |
|||
def lcm(m, n) |
|||
return (m * n) / gcd(m, n) |
|||
end |
|||
println lcm(12, 18) |
|||
println lcm(6, 14) |
|||
println lcm(1,2) = lcm(2,1)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>36 |
|||
42 |
|||
true</pre> |
|||
=={{header|NetRexx}}== |
=={{header|NetRexx}}== |
||
< |
<syntaxhighlight lang="netrexx">/* NetRexx */ |
||
options replace format comments java crossref symbols nobinary |
options replace format comments java crossref symbols nobinary |
||
Line 1,398: | Line 2,144: | ||
return |
return |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,422: | Line 2,168: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
The standard module "math" provides a function "lcm" for two integers and for an open array of integers. If we absolutely want to compute the least common multiple with our own procedure, it can be done this way (less efficient than the function in the standard library which avoids the modulo): |
|||
<lang nim>proc gcd(u, v): auto = |
|||
<syntaxhighlight lang="nim">proc gcd(u, v: int): auto = |
|||
var |
var |
||
t = 0 |
|||
u = u |
u = u |
||
v = v |
v = v |
||
while v != 0: |
while v != 0: |
||
u = u %% v |
|||
swap u, v |
|||
v = t %% v |
|||
abs(u) |
abs(u) |
||
proc lcm(a, b): auto = abs(a * b) div gcd(a, b) |
proc lcm(a, b: int): auto = abs(a * b) div gcd(a, b) |
||
echo lcm(12, 18) |
echo lcm(12, 18) |
||
echo lcm(-6, 14)</ |
echo lcm(-6, 14)</syntaxhighlight> |
||
{{out}} |
|||
<pre>36 |
|||
42</pre> |
|||
=={{header|Objeck}}== |
=={{header|Objeck}}== |
||
{{trans|C}} |
{{trans|C}} |
||
< |
<syntaxhighlight lang="objeck"> |
||
class LCM { |
class LCM { |
||
function : Main(args : String[]) ~ Nil { |
function : Main(args : String[]) ~ Nil { |
||
Line 1,456: | Line 2,205: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
< |
<syntaxhighlight lang="ocaml">let rec gcd u v = |
||
if v <> 0 then (gcd v (u mod v)) |
if v <> 0 then (gcd v (u mod v)) |
||
else (abs u) |
else (abs u) |
||
Line 1,470: | Line 2,219: | ||
let () = |
let () = |
||
Printf.printf "lcm(35, 21) = %d\n" (lcm 21 35)</ |
Printf.printf "lcm(35, 21) = %d\n" (lcm 21 35)</syntaxhighlight> |
||
=={{header|Oforth}}== |
=={{header|Oforth}}== |
||
lcm is already defined into Integer class : |
lcm is already defined into Integer class : |
||
<lang |
<syntaxhighlight lang="oforth">12 18 lcm</syntaxhighlight> |
||
=={{header|ooRexx}}== |
=={{header|ooRexx}}== |
||
<syntaxhighlight lang="oorexx"> |
|||
<lang ooRexx> |
|||
say lcm(18, 12) |
say lcm(18, 12) |
||
Line 1,498: | Line 2,246: | ||
use arg x, y |
use arg x, y |
||
return x / gcd(x, y) * y |
return x / gcd(x, y) * y |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Order}}== |
=={{header|Order}}== |
||
{{trans|bc}} |
{{trans|bc}} |
||
< |
<syntaxhighlight lang="c">#include <order/interpreter.h> |
||
#define ORDER_PP_DEF_8gcd ORDER_PP_FN( \ |
#define ORDER_PP_DEF_8gcd ORDER_PP_FN( \ |
||
Line 1,515: | Line 2,263: | ||
// No support for negative numbers |
// No support for negative numbers |
||
ORDER_PP( 8to_lit(8lcm(12, 18)) ) // 36</ |
ORDER_PP( 8to_lit(8lcm(12, 18)) ) // 36</syntaxhighlight> |
||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
Built-in function: |
Built-in function: |
||
<lang |
<syntaxhighlight lang="parigp">lcm</syntaxhighlight> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
< |
<syntaxhighlight lang="pascal">Program LeastCommonMultiple(output); |
||
{$IFDEF FPC} |
|||
{$MODE DELPHI} |
|||
{$ENDIF} |
|||
function lcm(a, b: longint): longint; |
function lcm(a, b: longint): longint; |
||
begin |
|||
result := a; |
|||
while (result mod b) <> 0 do |
|||
inc(result, a); |
|||
end; |
|||
begin |
begin |
||
writeln('The least common multiple of 12 and 18 is: ', lcm(12, 18)); |
writeln('The least common multiple of 12 and 18 is: ', lcm(12, 18)); |
||
end.</ |
end.</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>The least common multiple of 12 and 18 is: 36 |
<pre>The least common multiple of 12 and 18 is: 36 |
||
</pre> |
|||
=={{header|PascalABC.NET}}== |
|||
<syntaxhighlight lang="delphi"> |
|||
function GCD(a,b: integer): integer; |
|||
begin |
|||
while b > 0 do |
|||
(a,b) := (b,a mod b); |
|||
Result := a; |
|||
end; |
|||
function LCM(a,b: integer): integer := a = 0 ? 0 : a div GCD(a,b) * b; |
|||
begin |
|||
Println(LCM(12,18)); |
|||
end. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
36 |
|||
</pre> |
</pre> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Using GCD: |
Using GCD: |
||
< |
<syntaxhighlight lang="perl">sub gcd { |
||
my ($ |
my ($x, $y) = @_; |
||
while ($ |
while ($x) { ($x, $y) = ($y % $x, $x) } |
||
$ |
$y |
||
} |
} |
||
sub lcm { |
sub lcm { |
||
my ($ |
my ($x, $y) = @_; |
||
($ |
($x && $y) and $x / gcd($x, $y) * $y or 0 |
||
} |
} |
||
print lcm(1001, 221);</ |
print lcm(1001, 221);</syntaxhighlight> |
||
Or by repeatedly increasing the smaller of the two until LCM is reached:< |
Or by repeatedly increasing the smaller of the two until LCM is reached:<syntaxhighlight lang="perl">sub lcm { |
||
use integer; |
use integer; |
||
my ($x, $y) = @_; |
my ($x, $y) = @_; |
||
my ($ |
my ($f, $s) = @_; |
||
while ($ |
while ($f != $s) { |
||
($ |
($f, $s, $x, $y) = ($s, $f, $y, $x) if $f > $s; |
||
$ |
$f = $s / $x * $x; |
||
$ |
$f += $x if $f < $s; |
||
} |
} |
||
$ |
$f |
||
} |
} |
||
print lcm(1001, 221);</ |
print lcm(1001, 221);</syntaxhighlight> |
||
=={{header| |
=={{header|Phix}}== |
||
It is a builtin function, defined in builtins\gcd.e and accepting either two numbers or a single sequence of any length. |
|||
This function is provided as an infix so that it can be used productively with various metaoperators. |
|||
<!--<syntaxhighlight lang="phix">(phixonline)--> |
|||
<lang Perl 6>say 3 lcm 4; # infix |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
say [lcm] 1..20; # reduction |
|||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">lcm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">18</span><span style="color: #0000FF;">)</span> |
|||
say ~(1..10 Xlcm 1..10) # cross</lang> |
|||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">lcm</span><span style="color: #0000FF;">({</span><span style="color: #000000;">12</span><span style="color: #0000FF;">,</span><span style="color: #000000;">18</span><span style="color: #0000FF;">})</span> |
|||
<!--</syntaxhighlight>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
36 |
|||
232792560 |
|||
36 |
|||
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> |
|||
</pre> |
|||
=={{header| |
=={{header|Phixmonti}}== |
||
<syntaxhighlight lang="phixmonti">def gcd /# u v -- n #/ |
|||
<lang Phix>function lcm(integer m, integer n) |
|||
abs int swap abs int swap |
|||
return m / gcd(m, n) * n |
|||
end function</lang> |
|||
dup |
|||
while |
|||
over over mod rot drop dup |
|||
endwhile |
|||
drop |
|||
enddef |
|||
def lcm /# m n -- n #/ |
|||
over over gcd rot swap / * |
|||
enddef |
|||
12345 50 lcm print</syntaxhighlight> |
|||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
{{trans|D}} |
{{trans|D}} |
||
< |
<syntaxhighlight lang="php">echo lcm(12, 18) == 36; |
||
function lcm($m, $n) { |
function lcm($m, $n) { |
||
Line 1,598: | Line 2,385: | ||
} |
} |
||
return $a; |
return $a; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Picat}}== |
|||
Picat has a built-in function <code>gcd/2</code>. |
|||
===Function=== |
|||
<syntaxhighlight lang="picat">lcm(X,Y)= abs(X*Y)//gcd(X,Y).</syntaxhighlight> |
|||
===Predicate=== |
|||
<syntaxhighlight lang="picat">lcm(X,Y,LCM) => LCM = abs(X*Y)//gcd(X,Y).</syntaxhighlight> |
|||
===Functional (fold/3)=== |
|||
<syntaxhighlight lang="picat">lcm(List) = fold(lcm,1,List).</syntaxhighlight> |
|||
===Test=== |
|||
<syntaxhighlight lang="picat">go => |
|||
L = [ |
|||
[12,18], |
|||
[-6,14], |
|||
[35,0], |
|||
[7,10], |
|||
[2562047788015215500854906332309589561,6795454494268282920431565661684282819] |
|||
], |
|||
foreach([X,Y] in L) |
|||
println((X,Y)=lcm(X,Y)) |
|||
end, |
|||
println('1..20'=lcm(1..20)), |
|||
println('1..50'=lcm(1..50)), |
|||
nl. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>(12,18) = 36 |
|||
(-6,14) = 42 |
|||
(35,0) = 0 |
|||
(7,10) = 70 |
|||
(2562047788015215500854906332309589561,6795454494268282920431565661684282819) = 15669251240038298262232125175172002594731206081193527869 |
|||
1..20 = 232792560 |
|||
1..50 = 3099044504245996706400</pre> |
|||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
Using 'gcd' from [[Greatest common divisor#PicoLisp]]: |
Using 'gcd' from [[Greatest common divisor#PicoLisp]]: |
||
< |
<syntaxhighlight lang="picolisp">(de lcm (A B) |
||
(abs (*/ A B (gcd A B))) )</ |
(abs (*/ A B (gcd A B))) )</syntaxhighlight> |
||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
<syntaxhighlight lang="pl/i"> |
|||
<lang PL/I> |
|||
/* Calculate the Least Common Multiple of two integers. */ |
/* Calculate the Least Common Multiple of two integers. */ |
||
Line 1,631: | Line 2,457: | ||
end GCD; |
end GCD; |
||
end LCM; |
end LCM; |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre> |
<pre> |
||
The LCM of 14 and 35 is 70 |
The LCM of 14 and 35 is 70 |
||
Line 1,638: | Line 2,464: | ||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
===version 1=== |
===version 1=== |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
function gcd ($a, $b) { |
function gcd ($a, $b) { |
||
function pgcd ($n, $m) { |
function pgcd ($n, $m) { |
||
Line 1,655: | Line 2,481: | ||
} |
} |
||
lcm 12 18 |
lcm 12 18 |
||
</syntaxhighlight> |
|||
</lang> |
|||
===version 2=== |
===version 2=== |
||
version2 is faster than version1 |
version2 is faster than version1 |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
function gcd ($a, $b) { |
function gcd ($a, $b) { |
||
function pgcd ($n, $m) { |
function pgcd ($n, $m) { |
||
Line 1,677: | Line 2,503: | ||
} |
} |
||
lcm 12 18 |
lcm 12 18 |
||
</syntaxhighlight> |
|||
</lang> |
|||
<b>Output:</b> |
<b>Output:</b> |
||
Line 1,686: | Line 2,512: | ||
=={{header|Prolog}}== |
=={{header|Prolog}}== |
||
SWI-Prolog knows gcd. |
SWI-Prolog knows gcd. |
||
< |
<syntaxhighlight lang="prolog">lcm(X, Y, Z) :- |
||
Z is abs(X * Y) / gcd(X,Y).</ |
Z is abs(X * Y) / gcd(X,Y).</syntaxhighlight> |
||
Example: |
Example: |
||
Line 1,693: | Line 2,519: | ||
Z = 36. |
Z = 36. |
||
</pre> |
</pre> |
||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
< |
<syntaxhighlight lang="purebasic">Procedure GCDiv(a, b); Euclidean algorithm |
||
Protected r |
Protected r |
||
While b |
While b |
||
Line 1,710: | Line 2,537: | ||
EndIf |
EndIf |
||
ProcedureReturn t*Sign(t) |
ProcedureReturn t*Sign(t) |
||
EndProcedure</ |
EndProcedure</syntaxhighlight> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
=== |
===Functional=== |
||
====gcd==== |
|||
Using the fractions libraries [http://docs.python.org/library/fractions.html?highlight=fractions.gcd#fractions.gcd gcd] function: |
Using the fractions libraries [http://docs.python.org/library/fractions.html?highlight=fractions.gcd#fractions.gcd gcd] function: |
||
< |
<syntaxhighlight lang="python">>>> import fractions |
||
>>> def lcm(a,b): return abs(a * b) / fractions.gcd(a,b) if a and b else 0 |
>>> def lcm(a,b): return abs(a * b) / fractions.gcd(a,b) if a and b else 0 |
||
Line 1,723: | Line 2,551: | ||
42 |
42 |
||
>>> assert lcm(0, 2) == lcm(2, 0) == 0 |
>>> assert lcm(0, 2) == lcm(2, 0) == 0 |
||
>>> </ |
>>> </syntaxhighlight> |
||
Or, for compositional flexibility, a curried '''lcm''', expressed in terms of our own '''gcd''' function: |
|||
<syntaxhighlight lang="python">'''Least common multiple''' |
|||
from inspect import signature |
|||
# lcm :: Int -> Int -> Int |
|||
def lcm(x): |
|||
'''The smallest positive integer divisible |
|||
without remainder by both x and y. |
|||
''' |
|||
return lambda y: 0 if 0 in (x, y) else abs( |
|||
y * (x // gcd_(x)(y)) |
|||
) |
|||
# gcd_ :: Int -> Int -> Int |
|||
def gcd_(x): |
|||
'''The greatest common divisor in terms of |
|||
the divisibility preordering. |
|||
''' |
|||
def go(a, b): |
|||
return go(b, a % b) if 0 != b else a |
|||
return lambda y: go(abs(x), abs(y)) |
|||
# TEST ---------------------------------------------------- |
|||
# main :: IO () |
|||
def main(): |
|||
'''Tests''' |
|||
print( |
|||
fTable( |
|||
__doc__ + 's of 60 and [12..20]:' |
|||
)(repr)(repr)( |
|||
lcm(60) |
|||
)(enumFromTo(12)(20)) |
|||
) |
|||
pairs = [(0, 2), (2, 0), (-6, 14), (12, 18)] |
|||
print( |
|||
fTable( |
|||
'\n\n' + __doc__ + 's of ' + repr(pairs) + ':' |
|||
)(repr)(repr)( |
|||
uncurry(lcm) |
|||
)(pairs) |
|||
) |
|||
# GENERIC ------------------------------------------------- |
|||
# enumFromTo :: (Int, Int) -> [Int] |
|||
def enumFromTo(m): |
|||
'''Integer enumeration from m to n.''' |
|||
return lambda n: list(range(m, 1 + n)) |
|||
# uncurry :: (a -> b -> c) -> ((a, b) -> c) |
|||
def uncurry(f): |
|||
'''A function over a tuple, derived from |
|||
a vanilla or curried function. |
|||
''' |
|||
if 1 < len(signature(f).parameters): |
|||
return lambda xy: f(*xy) |
|||
else: |
|||
return lambda xy: f(xy[0])(xy[1]) |
|||
# unlines :: [String] -> String |
|||
def unlines(xs): |
|||
'''A single string derived by the intercalation |
|||
of a list of strings with the newline character. |
|||
''' |
|||
return '\n'.join(xs) |
|||
# FORMATTING ---------------------------------------------- |
|||
# fTable :: String -> (a -> String) -> |
|||
# (b -> String) -> (a -> b) -> [a] -> String |
|||
def fTable(s): |
|||
'''Heading -> x display function -> fx display function -> |
|||
f -> xs -> tabular string. |
|||
''' |
|||
def go(xShow, fxShow, f, xs): |
|||
ys = [xShow(x) for x in xs] |
|||
w = max(map(len, ys)) |
|||
return s + '\n' + '\n'.join(map( |
|||
lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)), |
|||
xs, ys |
|||
)) |
|||
return lambda xShow: lambda fxShow: lambda f: lambda xs: go( |
|||
xShow, fxShow, f, xs |
|||
) |
|||
# MAIN --- |
|||
if __name__ == '__main__': |
|||
main()</syntaxhighlight> |
|||
{{Out}} |
|||
<pre>Least common multiples of 60 and [12..20]: |
|||
12 -> 60 |
|||
13 -> 780 |
|||
14 -> 420 |
|||
15 -> 60 |
|||
16 -> 240 |
|||
17 -> 1020 |
|||
18 -> 180 |
|||
19 -> 1140 |
|||
20 -> 60 |
|||
Least common multiples of [(0, 2), (2, 0), (-6, 14), (12, 18)]: |
|||
(0, 2) -> 0 |
|||
(2, 0) -> 0 |
|||
(-6, 14) -> 42 |
|||
(12, 18) -> 36</pre> |
|||
=== |
===Procedural=== |
||
====Prime decomposition==== |
|||
This imports [[Prime decomposition#Python]] |
This imports [[Prime decomposition#Python]] |
||
< |
<syntaxhighlight lang="python">from prime_decomposition import decompose |
||
try: |
try: |
||
reduce |
reduce |
||
Line 1,748: | Line 2,694: | ||
print( lcm(12, 18) ) # 36 |
print( lcm(12, 18) ) # 36 |
||
print( lcm(-6, 14) ) # 42 |
print( lcm(-6, 14) ) # 42 |
||
assert lcm(0, 2) == lcm(2, 0) == 0</ |
assert lcm(0, 2) == lcm(2, 0) == 0</syntaxhighlight> |
||
===Iteration over multiples=== |
====Iteration over multiples==== |
||
< |
<syntaxhighlight lang="python">>>> def lcm(*values): |
||
values = set([abs(int(v)) for v in values]) |
values = set([abs(int(v)) for v in values]) |
||
if values and 0 not in values: |
if values and 0 not in values: |
||
Line 1,769: | Line 2,715: | ||
>>> lcm(12, 18, 22) |
>>> lcm(12, 18, 22) |
||
396 |
396 |
||
>>> </ |
>>> </syntaxhighlight> |
||
===Repeated modulo=== |
====Repeated modulo==== |
||
{{trans|Tcl}} |
{{trans|Tcl}} |
||
< |
<syntaxhighlight lang="python">>>> def lcm(p,q): |
||
p, q = abs(p), abs(q) |
p, q = abs(p), abs(q) |
||
m = p * q |
m = p * q |
||
Line 1,790: | Line 2,736: | ||
>>> lcm(2, 0) |
>>> lcm(2, 0) |
||
0 |
0 |
||
>>> </ |
>>> </syntaxhighlight> |
||
=={{header|Qi}}== |
=={{header|Qi}}== |
||
<syntaxhighlight lang="qi"> |
|||
<lang qi> |
|||
(define gcd |
(define gcd |
||
A 0 -> A |
A 0 -> A |
||
Line 1,799: | Line 2,745: | ||
(define lcm A B -> (/ (* A B) (gcd A B))) |
(define lcm A B -> (/ (* A B) (gcd A B))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Quackery}}== |
|||
<syntaxhighlight lang="quackery">[ [ dup while |
|||
tuck mod again ] |
|||
drop abs ] is gcd ( n n --> n ) |
|||
[ 2dup and iff |
|||
[ 2dup gcd |
|||
/ * abs ] |
|||
else and ] is lcm ( n n --> n )</syntaxhighlight> |
|||
=={{header|R}}== |
=={{header|R}}== |
||
<syntaxhighlight lang="r"> |
|||
<lang R> |
|||
"%gcd%" <- function(u, v) {ifelse(u %% v != 0, v %gcd% (u%%v), v)} |
"%gcd%" <- function(u, v) {ifelse(u %% v != 0, v %gcd% (u%%v), v)} |
||
Line 1,807: | Line 2,765: | ||
print (50 %lcm% 75) |
print (50 %lcm% 75) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
Racket already has defined both lcm and gcd funtions: |
Racket already has defined both lcm and gcd funtions: |
||
< |
<syntaxhighlight lang="racket">#lang racket |
||
(lcm 3 4 5 6) ;returns 60 |
(lcm 3 4 5 6) ;returns 60 |
||
(lcm 8 108) ;returns 216 |
(lcm 8 108) ;returns 216 |
||
(gcd 8 108) ;returns 4 |
(gcd 8 108) ;returns 4 |
||
(gcd 108 216 432) ;returns 108</ |
(gcd 108 216 432) ;returns 108</syntaxhighlight> |
||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
This function is provided as an infix so that it can be used productively with various metaoperators. |
|||
<syntaxhighlight lang="raku" line>say 3 lcm 4; # infix |
|||
say [lcm] 1..20; # reduction |
|||
say ~(1..10 Xlcm 1..10) # cross</syntaxhighlight> |
|||
{{out}} |
|||
<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|Retro}}== |
=={{header|Retro}}== |
||
This is from the math extensions library included with Retro. |
This is from the math extensions library included with Retro. |
||
< |
<syntaxhighlight lang="retro">: gcd ( ab-n ) [ tuck mod dup ] while drop ; |
||
: lcm ( ab-n ) 2over gcd [ * ] dip / ;</ |
: lcm ( ab-n ) 2over gcd [ * ] dip / ;</syntaxhighlight> |
||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
Line 1,830: | Line 2,799: | ||
Usage note: the integers can be expressed as a list and/or specified as individual arguments (or as mixed). |
Usage note: the integers can be expressed as a list and/or specified as individual arguments (or as mixed). |
||
< |
<syntaxhighlight lang="rexx">/*REXX program finds the LCM (Least Common Multiple) of any number of integers. */ |
||
numeric digits 10000 /*can handle 10k decimal digit numbers.*/ |
numeric digits 10000 /*can handle 10k decimal digit numbers.*/ |
||
say 'the LCM of 19 and 0 is ───► ' lcm(19 0 ) |
say 'the LCM of 19 and 0 is ───► ' lcm(19 0 ) |
||
Line 1,846: | Line 2,815: | ||
x=abs(x) /*use the absolute value of X. */ |
x=abs(x) /*use the absolute value of X. */ |
||
do while $\=='' /*process the remainder of args. */ |
do while $\=='' /*process the remainder of args. */ |
||
parse var $ ! $; |
parse var $ ! $; if !<0 then !=-! /*pick off the next arg (ABS val).*/ |
||
if !==0 then return 0 /*if zero, then LCM is also zero. */ |
if !==0 then return 0 /*if zero, then LCM is also zero. */ |
||
d=x*! /*calculate part of the LCM here. */ |
d=x*! /*calculate part of the LCM here. */ |
||
Line 1,853: | Line 2,822: | ||
x=d%x /*divide the pre─calculated value.*/ |
x=d%x /*divide the pre─calculated value.*/ |
||
end /*while*/ /* [↑] process subsequent args. */ |
end /*while*/ /* [↑] process subsequent args. */ |
||
return x /*return with the LCM of the args.*/</ |
return x /*return with the LCM of the args.*/</syntaxhighlight> |
||
'''output''' when using the (internal) supplied list: |
'''output''' when using the (internal) supplied list: |
||
<pre> |
<pre> |
||
Line 1,868: | Line 2,837: | ||
{{trans|REXX version 0}} using different argument handling- |
{{trans|REXX version 0}} using different argument handling- |
||
Use as lcm(a,b,c,---) |
Use as lcm(a,b,c,---) |
||
< |
<syntaxhighlight lang="rexx">lcm2: procedure |
||
x=abs(arg(1)) |
x=abs(arg(1)) |
||
do k=2 to arg() While x<>0 |
do k=2 to arg() While x<>0 |
||
Line 1,888: | Line 2,857: | ||
end |
end |
||
end |
end |
||
return x</ |
return x</syntaxhighlight> |
||
===versions 1 and 2 compared=== |
|||
The ''(performance) improvement'' of version 2 is due to the different argument handling at the cost of less ''freedom'' of argument specification (you must use lcm2(a,b,c) instead of the ''possible'' lcm1(a b,c). Consider, however, lcm1(3 -4, 5) which, of course, won't work as possibly intended. |
|||
<br>The performance improvement is more significant with ooRexx than with Regina. |
|||
<br> ''Note:'' $ in version 1 was replaced by d in order to adapt it for this test with ooRexx. |
|||
<lang rexx>Parse Version v |
|||
Say 'Version='v |
|||
Call time 'R' |
|||
Do a=0 To 100 |
|||
Do b=0 To 100 |
|||
Do c=0 To 100 |
|||
x1.a.b.c=lcm1(a,b,c) |
|||
End |
|||
End |
|||
End |
|||
Say 'version 1' time('E') |
|||
Call time 'R' |
|||
Do a=0 To 100 |
|||
Do b=0 To 100 |
|||
Do c=0 To 100 |
|||
x2.a.b.c=lcm2(a,b,c) |
|||
End |
|||
End |
|||
End |
|||
Say 'version 2' time('E') |
|||
cnt.=0 |
|||
Do a=0 To 100 |
|||
Do b=0 To 100 |
|||
Do c=0 To 100 |
|||
If x1.a.b.c=x2.a.b.c then cnt.0ok=cnt.0ok+1 |
|||
End |
|||
End |
|||
End |
|||
Say cnt.0ok 'comparisons ok' |
|||
Exit |
|||
/*----------------------------------LCM subroutine----------------------*/ |
|||
lcm1: procedure; d=strip(arg(1) arg(2)); do i=3 to arg(); d=d arg(i); end |
|||
parse var d x d /*obtain the first value in args.*/ |
|||
x=abs(x) /*use the absolute value of X. */ |
|||
do while d\=='' /*process the rest of the args. */ |
|||
parse var d ! d; !=abs(!) /*pick off the next arg (ABS val)*/ |
|||
if !==0 then return 0 /*if zero, then LCM is also zero.*/ |
|||
x=x*!/gcd1(x,!) /*have GCD do the heavy lifting.*/ |
|||
end /*while*/ |
|||
return x /*return with LCM of arguments.*/ |
|||
/*----------------------------------GCD subroutine----------------------*/ |
|||
gcd1: procedure; d=strip(arg(1) arg(2)); do j=3 to arg(); d=d arg(j); end |
|||
parse var d x d /*obtain the first value in args.*/ |
|||
x=abs(x) /*use the absolute value of X. */ |
|||
do while d\=='' /*process the rest of the args. */ |
|||
parse var d y d; y=abs(y) /*pick off the next arg (ABS val)*/ |
|||
if y==0 then iterate /*if zero, then ignore the value.*/ |
|||
do until y==0; parse value x//y y with y x; end |
|||
end /*while*/ |
|||
return x /*return with GCD of arguments.*/ |
|||
lcm2: procedure |
|||
x=abs(arg(1)) |
|||
do k=2 to arg() While x<>0 |
|||
y=abs(arg(k)) |
|||
x=x*y/gcd2(x,y) |
|||
end |
|||
return x |
|||
gcd2: procedure |
|||
x=abs(arg(1)) |
|||
do j=2 to arg() |
|||
y=abs(arg(j)) |
|||
If y<>0 Then Do |
|||
do until z==0 |
|||
z=x//y |
|||
x=y |
|||
y=z |
|||
end |
|||
end |
|||
end |
|||
return x</lang> |
|||
{{out}} |
|||
Output of rexx lcmt and regina lcmt cut and pasted together: |
|||
<pre>Version=REXX-ooRexx_4.2.0(MT)_32-bit 6.04 22 Feb 2014 |
|||
Version=REXX-Regina_3.9.0(MT) 5.00 16 Oct 2014 |
|||
version 1 29.652000 version 1 23.821000 |
|||
version 2 10.857000 version 2 21.209000 |
|||
1030301 comparisons ok 1030301 comparisons ok</pre> |
|||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
<lang> |
<syntaxhighlight lang="text"> |
||
see lcm(24,36) |
see lcm(24,36) |
||
Line 1,989: | Line 2,874: | ||
end |
end |
||
return gcd |
return gcd |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|RPL}}== |
|||
'''For unsigned integers''' |
|||
≪ DUP2 < ≪ SWAP ≫ IFT |
|||
'''WHILE''' DUP B→R '''REPEAT''' |
|||
SWAP OVER / LAST ROT * - '''END''' DROP |
|||
≫ '<span style="color:blue">GCD</span>' STO |
|||
≪ DUP2 * ROT ROT <span style="color:blue">GCD</span> / |
|||
≫ '<span style="color:blue">LCM</span>' STO |
|||
#12d #18d <span style="color:blue">LCM</span> |
|||
{{out}} |
|||
<pre> |
|||
1: #36d |
|||
</pre> |
|||
'''For usual integers''' (floating point without decimal part) |
|||
≪ '''WHILE''' DUP '''REPEAT''' |
|||
SWAP OVER MOD '''END''' DROP ABS |
|||
≫ '<span style="color:blue">GCD</span>' STO |
|||
≪ DUP2 * ROT ROT <span style="color:blue">GCD</span> / |
|||
≫ '<span style="color:blue">LCM</span>' STO |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
Ruby has an <tt>Integer#lcm</tt> method, which finds the least common multiple of two integers. |
Ruby has an <tt>Integer#lcm</tt> method, which finds the least common multiple of two integers. |
||
< |
<syntaxhighlight lang="ruby">irb(main):001:0> 12.lcm 18 |
||
=> 36</ |
=> 36</syntaxhighlight> |
||
I can also write my own <tt>lcm</tt> method. This one takes any number of arguments. |
I can also write my own <tt>lcm</tt> method. This one takes any number of arguments. |
||
< |
<syntaxhighlight lang="ruby">def gcd(m, n) |
||
m, n = n, m % n until n.zero? |
m, n = n, m % n until n.zero? |
||
m.abs |
m.abs |
||
Line 2,012: | Line 2,920: | ||
p lcm 12, 18, 22 |
p lcm 12, 18, 22 |
||
p lcm 15, 14, -6, 10, 21</ |
p lcm 15, 14, -6, 10, 21</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,021: | Line 2,929: | ||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||
{{works with|Just BASIC}} |
|||
<lang runbasic>print lcm(22,44) |
|||
{{works with|Liberty BASIC}} |
|||
<syntaxhighlight lang="lb">print "lcm( 12, -18) = "; lcm( 12, -18) |
|||
print "lcm( 15, 12) = "; lcm( 15, 12) |
|||
print "lcm(-10, -14) = "; lcm(-10, -14) |
|||
print "lcm( 0, 1) = "; lcm( 0, 1) |
|||
end |
|||
function lcm(m,n) |
function lcm(m, n) |
||
lcm = abs(m * n) / GCD(m, n) |
|||
while n |
|||
end function |
|||
t = m |
|||
m = n |
|||
n = t mod n |
|||
wend |
|||
lcm = m |
|||
end function</lang> |
|||
function GCD(a, b) |
|||
while b |
|||
c = a |
|||
a = b |
|||
b = c mod b |
|||
wend |
|||
GCD = abs(a) |
|||
end function</syntaxhighlight> |
|||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
This implementation uses a recursive implementation of Stein's algorithm to calculate the gcd. |
This implementation uses a recursive implementation of Stein's algorithm to calculate the gcd. |
||
< |
<syntaxhighlight lang="rust">use std::cmp::{max, min}; |
||
fn gcd_stein(a: usize, b: usize) -> usize { |
|||
fn gcd(a: usize, b: usize) -> usize { |
|||
match ((a, b), (a & 1, b & 1)) { |
match ((a, b), (a & 1, b & 1)) { |
||
((x, y), _) if x == y |
((x, y), _) if x == y => y, |
||
((0, x), _) | ((x, 0), _) |
((0, x), _) | ((x, 0), _) => x, |
||
((x, y), (0, 1)) | ((y, x), (1, 0)) => gcd(x >> 1, y), |
((x, y), (0, 1)) | ((y, x), (1, 0)) => gcd(x >> 1, y), |
||
((x, y), (0, 0)) |
((x, y), (0, 0)) => gcd(x >> 1, y >> 1) << 1, |
||
((x, y), (1, 1)) |
((x, y), (1, 1)) => { |
||
let (x, y) = (min(x, y), max(x, y)); |
|||
gcd((y - x) >> 1, x) |
|||
} |
|||
_ => unreachable!(), |
|||
_ => unreachable!(), |
|||
} |
} |
||
} |
} |
||
fn lcm(a: usize, b: usize) -> usize { |
fn lcm(a: usize, b: usize) -> usize { |
||
a * b / |
a * b / gcd(a, b) |
||
} |
|||
}</lang> |
|||
fn main() { |
|||
println!("{}", lcm(6324, 234)) |
|||
}</syntaxhighlight> |
|||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight 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)</ |
def lcm(a: Int, b: Int)=(a*b).abs/gcd(a,b)</syntaxhighlight> |
||
< |
<syntaxhighlight lang="scala">lcm(12, 18) // 36 |
||
lcm( 2, 0) // 0 |
lcm( 2, 0) // 0 |
||
lcm(-6, 14) // 42</ |
lcm(-6, 14) // 42</syntaxhighlight> |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
<lang |
<syntaxhighlight lang="scheme"> |
||
>(define gcd (lambda (a b) |
|||
216</lang> |
|||
(if (zero? b) |
|||
a |
|||
(gcd b (remainder a b))))) |
|||
>(define lcm (lambda (a b) |
|||
(if (or (zero? a) (zero? b)) |
|||
0 |
|||
(abs (* b (floor (/ a (gcd a b)))))))) |
|||
>(lcm 12 18) |
|||
36</syntaxhighlight> |
|||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
< |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const func integer: gcd (in var integer: a, in var integer: b) is func |
const func integer: gcd (in var integer: a, in var integer: b) is func |
||
Line 2,086: | Line 3,019: | ||
begin |
begin |
||
writeln("lcm(35, 21) = " <& lcm(21, 35)); |
writeln("lcm(35, 21) = " <& lcm(21, 35)); |
||
end func;</ |
end func;</syntaxhighlight> |
||
Original source: [http://seed7.sourceforge.net/algorith/math.htm#lcm] |
Original source: [http://seed7.sourceforge.net/algorith/math.htm#lcm] |
||
=={{header|SenseTalk}}== |
|||
<syntaxhighlight lang="sensetalk">function gcd m, n |
|||
repeat while m is greater than 0 |
|||
put m into temp |
|||
put n modulo m into m |
|||
put temp into n |
|||
end repeat |
|||
return n |
|||
end gcd |
|||
function lcm m, n |
|||
return m divided by gcd(m, n) times n |
|||
end lcm</syntaxhighlight> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
Built-in: |
Built-in: |
||
< |
<syntaxhighlight lang="ruby">say Math.lcm(1001, 221)</syntaxhighlight> |
||
Using GCD: |
Using GCD: |
||
< |
<syntaxhighlight lang="ruby">func gcd(a, b) { |
||
while (a) { (a, b) = (b % a, a) } |
while (a) { (a, b) = (b % a, a) } |
||
return b |
return b |
||
Line 2,104: | Line 3,051: | ||
} |
} |
||
say lcm(1001, 221)</ |
say lcm(1001, 221)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,112: | Line 3,059: | ||
=={{header|Smalltalk}}== |
=={{header|Smalltalk}}== |
||
Smalltalk has a built-in <code>lcm</code> method on <code>SmallInteger</code>: |
Smalltalk has a built-in <code>lcm</code> method on <code>SmallInteger</code>: |
||
<lang |
<syntaxhighlight lang="smalltalk">12 lcm: 18</syntaxhighlight> |
||
=={{header|Sparkling}}== |
=={{header|Sparkling}}== |
||
< |
<syntaxhighlight lang="sparkling">function factors(n) { |
||
var f = {}; |
var f = {}; |
||
Line 2,147: | Line 3,094: | ||
function LCM(n, k) { |
function LCM(n, k) { |
||
return n * k / GCD(n, k); |
return n * k / GCD(n, k); |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Standard ML}}== |
|||
===Readable version=== |
|||
<syntaxhighlight lang="sml">fun gcd (0,n) = n |
|||
| gcd (m,n) = gcd(n mod m, m) |
|||
fun lcm (m,n) = abs(x * y) div gcd (m, n)</syntaxhighlight> |
|||
===Alternate version=== |
|||
<syntaxhighlight lang="sml">val rec gcd = fn (x, 0) => abs x | p as (_, y) => gcd (y, Int.rem p) |
|||
val lcm = fn p as (x, y) => Int.quot (abs (x * y), gcd p)</syntaxhighlight> |
|||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
Using the Swift GCD function. |
Using the Swift GCD function. |
||
< |
<syntaxhighlight lang="swift">func lcm(a:Int, b:Int) -> Int { |
||
return abs(a * b) / gcd_rec(a, b) |
return abs(a * b) / gcd_rec(a, b) |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
< |
<syntaxhighlight lang="tcl">proc lcm {p q} { |
||
set m [expr {$p * $q}] |
set m [expr {$p * $q}] |
||
if {!$m} {return 0} |
if {!$m} {return 0} |
||
Line 2,164: | Line 3,124: | ||
if {!$q} {return [expr {$m / $p}]} |
if {!$q} {return [expr {$m / $p}]} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Demonstration |
Demonstration |
||
<lang |
<syntaxhighlight lang="tcl">puts [lcm 12 18]</syntaxhighlight> |
||
Output: |
Output: |
||
36 |
36 |
||
=={{header|TI-83 BASIC}}== |
=={{header|TI-83 BASIC}}== |
||
< |
<syntaxhighlight lang="ti83b">lcm(12,18 |
||
36</ |
36</syntaxhighlight> |
||
=={{header|TSE SAL}}== |
=={{header|TSE SAL}}== |
||
< |
<syntaxhighlight 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 ) |
INTEGER PROC FNMathGetLeastCommonMultipleI( INTEGER x1I, INTEGER x2I ) |
||
// |
// |
||
Line 2,204: | Line 3,164: | ||
Warn( FNMathGetLeastCommonMultipleI( Val( s1 ), Val( s2 ) ) ) // gives e.g. 10 |
Warn( FNMathGetLeastCommonMultipleI( Val( s1 ), Val( s2 ) ) ) // gives e.g. 10 |
||
UNTIL FALSE |
UNTIL FALSE |
||
END</ |
END</syntaxhighlight> |
||
=={{header|TXR}}== |
|||
<syntaxhighlight lang="bash">$ txr -p '(lcm (expt 2 123) (expt 6 49) 17)' |
|||
43259338018880832376582582128138484281161556655442781051813888</syntaxhighlight> |
|||
== {{header|TypeScript}} == |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="javascript">// Least common multiple |
|||
function gcd(m: number, n: number): number { |
|||
var tmp: number; |
|||
while (m != 0) { |
|||
tmp = m; |
|||
m = n % m; |
|||
n = tmp; |
|||
} |
|||
return n; |
|||
} |
|||
function lcm(m: number, n: number): number { |
|||
return Math.floor(m / gcd(m, n)) * n; |
|||
} |
|||
console.log(`LCM(35, 21) = ${lcm(35, 21)}`); |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
LCM(35, 21) = 105 |
|||
</pre> |
|||
=={{header|uBasic/4tH}}== |
=={{header|uBasic/4tH}}== |
||
{{trans|BBC BASIC}} |
{{trans|BBC BASIC}} |
||
<lang>Print "LCM of 12 : 18 = "; FUNC(_LCM(12,18)) |
<syntaxhighlight lang="text">Print "LCM of 12 : 18 = "; FUNC(_LCM(12,18)) |
||
End |
End |
||
Line 2,229: | Line 3,218: | ||
Else |
Else |
||
Return (0) |
Return (0) |
||
EndIf</ |
EndIf</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>LCM of 12 : 18 = 36 |
<pre>LCM of 12 : 18 = 36 |
||
0 OK, 0:330</pre> |
0 OK, 0:330</pre> |
||
=={{header|Uiua}}== |
|||
<syntaxhighlight lang="uiua"> |
|||
# Greatest Common Divisor using Euclidean algorithm |
|||
Gcd ← ⊙◌⍢(⟜◿:|±,) |
|||
# Least Common Multiple |
|||
Lcm ← ÷⊃(Gcd|⌵×) |
|||
</syntaxhighlight> |
|||
=={{header|UNIX Shell}}== |
=={{header|UNIX Shell}}== |
||
<math>\operatorname{lcm}(m, n) = \left | \frac{m \times n}{\operatorname{gcd}(m, n)} \right |</math> |
<math>\operatorname{lcm}(m, n) = \left | \frac{m \times n}{\operatorname{gcd}(m, n)} \right |</math> |
||
{{works with|Bourne Shell}} |
{{works with|Bourne Shell}} |
||
< |
<syntaxhighlight lang="bash">gcd() { |
||
# Calculate $1 % $2 until $2 becomes zero. |
# Calculate $1 % $2 until $2 becomes zero. |
||
until test 0 -eq "$2"; do |
until test 0 -eq "$2"; do |
||
Line 2,258: | Line 3,255: | ||
lcm 30 -42 |
lcm 30 -42 |
||
# => 210</ |
# => 210</syntaxhighlight> |
||
==={{header|C Shell}}=== |
==={{header|C Shell}}=== |
||
< |
<syntaxhighlight lang="csh">alias gcd eval \''set gcd_args=( \!*:q ) \\ |
||
@ gcd_u=$gcd_args[2] \\ |
@ gcd_u=$gcd_args[2] \\ |
||
@ gcd_v=$gcd_args[3] \\ |
@ gcd_v=$gcd_args[3] \\ |
||
Line 2,284: | Line 3,281: | ||
lcm result 30 -42 |
lcm result 30 -42 |
||
echo $result |
echo $result |
||
# => 210</ |
# => 210</syntaxhighlight> |
||
=={{header|Ursa}}== |
=={{header|Ursa}}== |
||
< |
<syntaxhighlight lang="ursa">import "math" |
||
out (lcm 12 18) endl console</ |
out (lcm 12 18) endl console</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>36</pre> |
<pre>36</pre> |
||
=={{header|Vala}}== |
=={{header|Vala}}== |
||
< |
<syntaxhighlight lang="vala"> |
||
int lcm(int a, int b){ |
int lcm(int a, int b){ |
||
/*Return least common multiple of two ints*/ |
/*Return least common multiple of two ints*/ |
||
Line 2,320: | Line 3,317: | ||
stdout.printf("lcm(%d, %d) = %d\n", a, b, lcm(a, b)); |
stdout.printf("lcm(%d, %d) = %d\n", a, b, lcm(a, b)); |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|VBA}}== |
|||
<syntaxhighlight lang="vb">Function gcd(u As Long, v As Long) As Long |
|||
Dim t As Long |
|||
Do While v |
|||
t = u |
|||
u = v |
|||
v = t Mod v |
|||
Loop |
|||
gcd = u |
|||
End Function |
|||
Function lcm(m As Long, n As Long) As Long |
|||
lcm = Abs(m * n) / gcd(m, n) |
|||
End Function</syntaxhighlight> |
|||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
< |
<syntaxhighlight lang="vb">Function LCM(a,b) |
||
LCM = POS((a * b)/GCD(a,b)) |
LCM = POS((a * b)/GCD(a,b)) |
||
End Function |
End Function |
||
Line 2,352: | Line 3,363: | ||
WScript.StdOut.Write "The LCM of " & i & " and " & j & " is " & LCM(i,j) & "." |
WScript.StdOut.Write "The LCM of " & i & " and " & j & " is " & LCM(i,j) & "." |
||
WScript.StdOut.WriteLine</ |
WScript.StdOut.WriteLine</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,369: | Line 3,380: | ||
=={{header|Wortel}}== |
=={{header|Wortel}}== |
||
Operator |
Operator |
||
<lang |
<syntaxhighlight lang="wortel">@lcm a b</syntaxhighlight> |
||
Number expression |
Number expression |
||
<lang |
<syntaxhighlight lang="wortel">!#~km a b</syntaxhighlight> |
||
Function (using gcd) |
Function (using gcd) |
||
< |
<syntaxhighlight lang="wortel">&[a b] *b /a @gcd a b</syntaxhighlight> |
||
=={{header|Wren}}== |
|||
<syntaxhighlight lang="wren">var gcd = Fn.new { |x, y| |
|||
while (y != 0) { |
|||
var t = y |
|||
y = x % y |
|||
x = t |
|||
} |
|||
return x.abs |
|||
} |
|||
var lcm = Fn.new { |x, y| |
|||
if (x == 0 && y == 0) return 0 |
|||
return (x*y).abs / gcd.call(x, y) |
|||
} |
|||
var xys = [[12, 18], [-6, 14], [35, 0]] |
|||
for (xy in xys) { |
|||
System.print("lcm(%(xy[0]), %(xy[1]))\t%("\b"*5) = %(lcm.call(xy[0], xy[1]))") |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
lcm(12, 18) = 36 |
|||
lcm(-6, 14) = 42 |
|||
lcm(35, 0) = 0 |
|||
</pre> |
|||
=={{header|XBasic}}== |
|||
{{trans|C}} |
|||
{{works with|Windows XBasic}} |
|||
<syntaxhighlight lang="xbasic">' Least common multiple |
|||
PROGRAM "leastcommonmultiple" |
|||
VERSION "0.0001" |
|||
DECLARE FUNCTION Entry() |
|||
INTERNAL FUNCTION Gcd(m&, n&) |
|||
INTERNAL FUNCTION Lcm(m&, n&) |
|||
FUNCTION Entry() |
|||
PRINT "LCM(35, 21) ="; Lcm(35, 21) |
|||
END FUNCTION |
|||
FUNCTION Gcd(m&, n&) |
|||
DO WHILE m& <> 0 |
|||
tmp& = m& |
|||
m& = n& MOD m& |
|||
n& = tmp& |
|||
LOOP |
|||
RETURN n& |
|||
END FUNCTION |
|||
FUNCTION Lcm(m&, n&) |
|||
RETURN m& / Gcd(m&, n&) * n& |
|||
END FUNCTION |
|||
END PROGRAM |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
LCM(35, 21) = 105 |
|||
</pre> |
|||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">include c:\cxpl\codes; |
||
func GCD(M,N); \Return the greatest common divisor of M and N |
func GCD(M,N); \Return the greatest common divisor of M and N |
||
Line 2,391: | Line 3,464: | ||
\Display the LCM of two integers entered on command line |
\Display the LCM of two integers entered on command line |
||
IntOut(0, LCM(IntIn(8), IntIn(8)))</ |
IntOut(0, LCM(IntIn(8), IntIn(8)))</syntaxhighlight> |
||
=={{header|Yabasic}}== |
|||
<syntaxhighlight lang="yabasic">sub gcd(u, v) |
|||
local t |
|||
u = int(abs(u)) |
|||
v = int(abs(v)) |
|||
while(v) |
|||
t = u |
|||
u = v |
|||
v = mod(t, v) |
|||
wend |
|||
return u |
|||
end sub |
|||
sub lcm(m, n) |
|||
return m / gcd(m, n) * n |
|||
end sub |
|||
print "Least common multiple: ", lcm(12345, 23044)</syntaxhighlight> |
|||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl">fcn lcm(m,n){ (m*n).abs()/m.gcd(n) } // gcd is a number method</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
Latest revision as of 17:21, 4 July 2024
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Compute the least common multiple (LCM) of two integers.
Given m and n, the least common multiple is the smallest positive integer that has both m and n as factors.
- 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.
One can also find lcm by merging the prime decompositions of both m and n.
- Related task
- See also
- MathWorld entry: Least Common Multiple.
- Wikipedia entry: Least common multiple.
11l
F gcd(=a, =b)
L b != 0
(a, b) = (b, a % b)
R a
F lcm(m, n)
R m I/ gcd(m, n) * n
print(lcm(12, 18))
- Output:
36
360 Assembly
For maximum compatibility, this program uses only the basic instruction set (S/360) with 2 ASSIST macros (XDECO,XPRNT).
LCM CSECT
USING LCM,R15 use calling register
L R6,A a
L R7,B b
LR R8,R6 c=a
LOOPW LR R4,R8 c
SRDA R4,32 shift to next reg
DR R4,R7 c/b
LTR R4,R4 while c mod b<>0
BZ ELOOPW leave while
AR R8,R6 c+=a
B LOOPW end while
ELOOPW LPR R9,R6 c=abs(u)
L R1,A a
XDECO R1,XDEC edit a
MVC PG+4(5),XDEC+7 move a to buffer
L R1,B b
XDECO R1,XDEC edit b
MVC PG+10(5),XDEC+7 move b to buffer
XDECO R8,XDEC edit c
MVC PG+17(10),XDEC+2 move c to buffer
XPRNT PG,80 print buffer
XR R15,R15 return code =0
BR R14 return to caller
A DC F'1764' a
B DC F'3920' b
PG DC CL80'lcm(00000,00000)=0000000000' buffer
XDEC DS CL12 temp for edit
YREGS
END LCM
- Output:
lcm( 1764, 3920)= 35280
8th
: gcd \ a b -- gcd
dup 0 n:= if drop ;; then
tuck \ b a b
n:mod \ b a-mod-b
recurse ;
: lcm \ m n
2dup \ m n m n
n:* \ m n m*n
n:abs \ m n abs(m*n)
-rot \ abs(m*n) m n
gcd \ abs(m*n) gcd(m.n)
n:/mod \ abs / gcd
nip \ abs div gcd
;
: demo \ n m --
2dup "LCM of " . . " and " . . " = " . lcm . ;
12 18 demo cr
-6 14 demo cr
35 0 demo cr
bye
- Output:
LCM of 18 and 12 = 36 LCM of 14 and -6 = 42 LCM of 0 and 35 = 0
Action!
CARD FUNC Lcm(CARD a,b)
CARD tmp,c
IF a=0 OR b=0 THEN
RETURN (0)
FI
IF a<b THEN
tmp=a a=b b=tmp
FI
c=0
DO
c==+1
UNTIL a*c MOD b=0
OD
RETURN(a*c)
PROC Test(CARD a,b)
CARD res
res=Lcm(a,b)
PrintF("LCM of %I and %I is %I%E",a,b,res)
RETURN
PROC Main()
Test(4,6)
Test(120,77)
Test(24,8)
Test(1,56)
Test(12,0)
RETURN
- Output:
Screenshot from Atari 8-bit computer
LCM of 4 and 6 is 12 LCM of 120 and 77 is 9240 LCM of 24 and 8 is 24 LCM of 1 and 56 is 56 LCM of 12 and 0 is 0
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
ALGOL 68
BEGIN
PROC gcd = (INT m, n) INT :
BEGIN
INT a := ABS m, b := ABS n;
IF a=0 OR b=0 THEN 0 ELSE
WHILE b /= 0 DO INT t = b; b := a MOD b; a := t OD;
a
FI
END;
PROC lcm = (INT m, n) INT : ( m*n = 0 | 0 | ABS (m*n) % gcd (m, n));
INT m=12, n=18;
printf (($gxg(0)3(xgxg(0))l$,
"The least common multiple of", m, "and", n, "is", lcm(m,n),
"and their greatest common divisor is", gcd(m,n)))
END
- Output:
The least common multiple of 12 and 18 is 36 and their greatest common divisor is 6
Note that either or both PROCs could just as easily be implemented as OPs but then the operator priorities would also have to be declared.
ALGOL W
begin
integer procedure gcd ( integer value a, b ) ;
if b = 0 then a else gcd( b, a rem abs(b) );
integer procedure lcm( integer value a, b ) ;
abs( a * b ) div gcd( a, b );
write( lcm( 15, 20 ) );
end.
APL
APL provides this function.
12^18
36
If for any reason we wanted to reimplement it, we could do so in terms of the greatest common divisor by transcribing the formula set out in the task specification into APL notation:
LCM←{(|⍺×⍵)÷⍺∨⍵}
12 LCM 18
36
AppleScript
------------------ LEAST COMMON MULTIPLE -----------------
-- lcm :: Integral a => a -> a -> a
on lcm(x, y)
if 0 = x or 0 = y then
0
else
abs(x div (gcd(x, y)) * y)
end if
end lcm
--------------------------- TEST -------------------------
on run
lcm(12, 18)
--> 36
end run
-------------------- GENERIC FUNCTIONS -------------------
-- abs :: Num a => a -> a
on abs(x)
if 0 > x then
-x
else
x
end if
end abs
-- gcd :: Integral a => a -> a -> a
on gcd(x, y)
script
on |λ|(a, b)
if 0 = b then
a
else
|λ|(b, a mod b)
end if
end |λ|
end script
result's |λ|(abs(x), abs(y))
end gcd
- Output:
36
Arendelle
For GCD function check out here
< a , b > ( return , abs ( @a * @b ) / !gcd( @a , @b ) )
Arturo
lcm: function [x,y][
x * y / gcd @[x y]
]
print lcm 12 18
- Output:
36
Assembly
x86 Assembly
; lcm.asm: calculates the least common multiple
; of two positive integers
;
; nasm x86_64 assembly (linux) with libc
; assemble: nasm -felf64 lcm.asm; gcc lcm.o
; usage: ./a.out [number1] [number2]
global main
extern printf ; c function: prints formatted output
extern strtol ; c function: converts strings to longs
section .text
main:
push rbp ; set up stack frame
; rdi contains argc
; if less than 3, exit
cmp rdi, 3
jl incorrect_usage
; push first argument as number
push rsi
mov rdi, [rsi+8]
mov rsi, 0
mov rdx, 10 ; base 10
call strtol
pop rsi
push rax
; push second argument as number
push rsi
mov rdi, [rsi+16]
mov rsi, 0
mov rdx, 10 ; base 10
call strtol
pop rsi
push rax
; pop arguments and call get_gcd
pop rdi
pop rsi
call get_gcd
; print value
mov rdi, print_number
mov rsi, rax
call printf
; exit
mov rax, 0 ; 0--exit success
pop rbp
ret
incorrect_usage:
mov rdi, bad_use_string
; rsi already contains argv
mov rsi, [rsi]
call printf
mov rax, 0 ; 0--exit success
pop rbp
ret
bad_use_string:
db "Usage: %s [number1] [number2]",10,0
print_number:
db "%d",10,0
get_gcd:
push rbp ; set up stack frame
mov rax, 0
jmp loop
loop:
; keep adding the first argument
; to itself until a multiple
; is found. then, return
add rax, rdi
push rax
mov rdx, 0
div rsi
cmp rdx, 0
pop rax
je gcd_found
jmp loop
gcd_found:
pop rbp
ret
ATS
Compile with ‘patscc -o lcm lcm.dats’
#define ATS_DYNLOADFLAG 0 (* No initialization is needed. *)
#include "share/atspre_define.hats"
#include "share/atspre_staload.hats"
(********************************************************************)
(* *)
(* Declarations. *)
(* *)
(* (These could be ported to a .sats file.) *)
(* *)
(* lcm for unsigned integer types without constraints. *)
extern fun {tk : tkind}
g0uint_lcm (u : g0uint tk,
v : g0uint tk) :<>
g0uint tk
(* The gcd template function to be expanded when g0uint_lcm is
expanded. Set it to your favorite gcd function. *)
extern fun {tk : tkind}
g0uint_lcm$gcd (u : g0uint tk,
v : g0uint tk) :<>
g0uint tk
(* lcm for signed integer types, giving unsigned results. *)
extern fun {tk_signed, tk_unsigned : tkind}
g0int_lcm (u : g0int tk_signed,
v : g0int tk_signed) :<>
g0uint tk_unsigned
overload lcm with g0uint_lcm
overload lcm with g0int_lcm
(********************************************************************)
(* *)
(* The implementations. *)
(* *)
implement {tk}
g0uint_lcm (u, v) =
let
val d = g0uint_lcm$gcd<tk> (u, v)
in
(* There is no need to take the absolute value, because this
implementation is strictly for unsigned integers. *)
(u * v) / d
end
implement {tk_signed, tk_unsigned}
g0int_lcm (u, v) =
let
extern castfn
unsigned :
g0int tk_signed -<> g0uint tk_unsigned
in
g0uint_lcm (unsigned (abs u), unsigned (abs v))
end
(********************************************************************)
(* *)
(* A test that it actually works. *)
(* *)
implement
main0 () =
let
implement {tk}
g0uint_lcm$gcd (u, v) =
(* An ugly gcd for the sake of demonstrating that it can be done
this way: Euclid’s algorithm written an the ‘Algol’ style,
which is not a natural style in ATS. Almost always you want
to write a tail-recursive function, instead. I did, however
find the ‘Algol’ style very useful when I was migrating
matrix routines from Fortran.
In reality, you would implement g0uint_lcm$gcd by having it
simply call whatever gcd template function you are using in
your program. *)
$effmask_all
begin
let
var x : g0uint tk = u
var y : g0uint tk = v
in
while (y <> 0)
let
val z = y
in
y := x mod z;
x := z
end;
x
end
end
in
assertloc (lcm (~6, 14) = 42U);
assertloc (lcm (2L, 0L) = 0ULL);
assertloc (lcm (12UL, 18UL) = 36UL);
assertloc (lcm (12, 22) = 132ULL);
assertloc (lcm (7ULL, 31ULL) = 217ULL)
end
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)
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)
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
BASIC
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
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%)
IS-BASIC
100 DEF LCM(A,B)=(A*B)/GCD(A,B)
110 DEF GCD(A,B)
120 DO WHILE B>0
130 LET T=B:LET B=MOD(A,B):LET A=T
140 LOOP
150 LET GCD=A
160 END DEF
170 PRINT LCM(12,18)
Tiny BASIC
10 PRINT "First number"
20 INPUT A
30 PRINT "Second number"
40 INPUT B
42 LET Q = A
44 LET R = B
50 IF Q<0 THEN LET Q=-Q
60 IF R<0 THEN LET R=-R
70 IF Q>R THEN GOTO 130
80 LET R = R - Q
90 IF Q=0 THEN GOTO 110
100 GOTO 50
110 LET U = (A*B)/R
111 IF U < 0 THEN LET U = - U
112 PRINT U
120 END
130 LET C=Q
140 LET Q=R
150 LET R=C
160 GOTO 70
BASIC256
Iterative solution
function mcm (m, n)
if m = 0 or n = 0 then return 0
if m < n then
t = m : m = n : n = t
end if
cont = 0
do
cont += 1
until (m * cont) mod n = 0
return m * cont
end function
print "lcm( 12, 18) = "; mcm( 12, -18)
print "lcm( 15, 12) = "; mcm( 15, 12)
print "lcm(-10, -14) = "; mcm(-10, -14)
print "lcm( 0, 1) = "; mcm( 0, 1)
- Output:
lcm( 12, 18) = 36 lcm( 15, 12) = 60 lcm(-10, -14) = -70 lcm( 0, 1) = 0
Recursive solution
Reuses code from Greatest_common_divisor#Recursive_solution and correctly handles negative arguments
function gcdp(a, b)
if b = 0 then return a
return gcdp(b, a mod b)
end function
function gcd(a, b)
return gcdp(abs(a), abs(b))
end function
function lcm(a, b)
return abs(a * b) / gcd(a, b)
end function
print "lcm( 12, -18) = "; lcm( 12, -18)
print "lcm( 15, 12) = "; lcm( 15, 12)
print "lcm(-10, -14) = "; lcm(-10, -14)
print "lcm( 0, 1) = "; lcm( 0, 1)
- Output:
lcm( 12, -18) = 36.0 lcm( 15, 12) = 60.0 lcm(-10, -14) = 70.0 lcm( 0, 1) = 0.0
Batch File
@echo off
setlocal enabledelayedexpansion
set num1=12
set num2=18
call :lcm %num1% %num2%
exit /b
:lcm <input1> <input2>
if %2 equ 0 (
set /a lcm = %num1%*%num2%/%1
echo LCM = !lcm!
pause>nul
goto :EOF
)
set /a res = %1 %% %2
call :lcm %2 %res%
goto :EOF
- Output:
LCM = 36
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)
}
BCPL
get "libhdr"
let lcm(m,n) =
m=0 -> 0,
n=0 -> 0,
abs(m*n) / gcd(m,n)
and gcd(m,n) =
n=0 -> m,
gcd(n, m rem n)
let start() be writef("%N*N", lcm(12, 18))
- Output:
36
Befunge
Inputs are limited to signed 16-bit integers.
&>:0`2*1-*:&>:#@!#._:0`2*1v
>28*:*:**+:28*>:*:*/\:vv*-<
|<:%/*:*:*82\%*:*:*82<<>28v
>$/28*:*:*/*.@^82::+**:*:*<
- Input:
12345 -23044
- Output:
345660
BQN
Lcm ← ×÷{𝕨(|𝕊⍟(>⟜0)⊣)𝕩}
Example:
12 Lcm 18
36
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
Brat
gcd = { a, b |
true? { a == 0 }
{ b }
{ gcd(b % a, a) }
}
lcm = { a, b |
a * b / gcd(a, b)
}
p lcm(12, 18) # 36
p lcm(14, 21) # 42
Bruijn
:import std/Math .
lcm [[=?1 1 (=?0 0 |(1 / (gcd 1 0) ⋅ 0))]]
:test ((lcm (+12) (+18)) =? (+36)) ([[1]])
:test ((lcm (+42) (+25)) =? (+1050)) ([[1]])
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;
}
C#
Using System;
class Program
{
static int gcd(int m, int n)
{
return n == 0 ? Math.Abs(m) : gcd(n, n % m);
}
static int lcm(int m, int n)
{
return Math.Abs(m * n) / gcd(m, n);
}
static void Main()
{
Console.WriteLine("lcm(12,18)=" + lcm(12,18));
}
}
- Output:
lcm(12,18)=36
C++
#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 !
Alternate solution
#include <cstdlib>
#include <iostream>
#include <tuple>
int gcd(int a, int b) {
a = abs(a);
b = abs(b);
while (b != 0) {
std::tie(a, b) = std::make_tuple(b, a % b);
}
return a;
}
int lcm(int a, int b) {
int c = gcd(a, b);
return c == 0 ? 0 : a / c * b;
}
int main() {
std::cout << "The least common multiple of 12 and 18 is " << lcm(12, 18) << ",\n"
<< "and their greatest common divisor is " << gcd(12, 18) << "!"
<< std::endl;
return 0;
}
Clojure
(defn gcd
[a b]
(if (zero? b)
a
(recur b, (mod a b))))
(defn lcm
[a b]
(/ (* a b) (gcd a b)))
;; to calculate the lcm for a variable number of arguments
(defn lcmv [& v] (reduce lcm v))
CLU
gcd = proc (m, n: int) returns (int)
m, n := int$abs(m), int$abs(n)
while n ~= 0 do m, n := n, m // n end
return(m)
end gcd
lcm = proc (m, n: int) returns (int)
if m=0 cor n=0
then return(0)
else return(int$abs(m*n) / gcd(m,n))
end
end lcm
start_up = proc ()
po: stream := stream$primary_output()
stream$putl(po, int$unparse(lcm(12, 18)))
end start_up
- Output:
36
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.
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.
Cowgol
include "cowgol.coh";
sub gcd(m: uint32, n: uint32): (r: uint32) is
while n != 0 loop
var t := m;
m := n;
n := t % n;
end loop;
r := m;
end sub;
sub lcm(m: uint32, n: uint32): (r: uint32) is
if m==0 or n==0 then
r := 0;
else
r := m*n / gcd(m,n);
end if;
end sub;
print_i32(lcm(12, 18));
print_nl();
- Output:
36
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
Dart
main() {
int x=8;
int y=12;
int z= gcd(x,y);
var lcm=(x*y)/z;
print('$lcm');
}
int gcd(int a,int b)
{
if(b==0)
return a;
if(b!=0)
return gcd(b,a%b);
}
Delphi
See Pascal.
DWScript
PrintLn(Lcm(12, 18));
Output:
36
Draco
proc gcd(word m, n) word:
word t;
while n /= 0 do
t := m;
m := n;
n := t % n
od;
m
corp
proc lcm(word m, n) word:
if m=0 or n=0
then 0
else m*n / gcd(m,n)
fi
corp
proc main() void:
writeln(lcm(12, 18))
corp
- Output:
36
EasyLang
func gcd a b .
while b <> 0
h = b
b = a mod b
a = h
.
return a
.
func lcm a b .
return a / gcd a b * b
.
print lcm 12 18
- Output:
36
EchoLisp
(lcm a b) is already here as a two arguments function. Use foldl to find the lcm of a list of numbers.
(lcm 0 9) → 0
(lcm 444 888)→ 888
(lcm 888 999) → 7992
(define (lcm* list) (foldl lcm (first list) list)) → lcm*
(lcm* '(444 888 999)) → 7992
Elena
ELENA 6.x :
import extensions;
import system'math;
gcd = (m,n => (n == 0) ? (m.Absolute) : (gcd(n,n.mod(m))));
lcm = (m,n => (m * n).Absolute / gcd(m,n));
public program()
{
console.printLine("lcm(12,18)=",lcm(12,18))
}
- Output:
lcm(12,18)=36
Elixir
defmodule RC do
def gcd(a,0), do: abs(a)
def gcd(a,b), do: gcd(b, rem(a,b))
def lcm(a,b), do: div(abs(a*b), gcd(a,b))
end
IO.puts RC.lcm(-12,15)
- Output:
60
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
ERRE
PROGRAM LCM
PROCEDURE GCD(A,B->GCD)
LOCAL C
WHILE B DO
C=A
A=B
B=C MOD B
END WHILE
GCD=ABS(A)
END PROCEDURE
PROCEDURE LCM(M,N->LCM)
IF M=0 OR N=0 THEN
LCM=0
EXIT PROCEDURE
ELSE
GCD(M,N->GCD)
LCM=ABS(M*N)/GCD
END IF
END PROCEDURE
BEGIN
LCM(18,12->LCM)
PRINT("LCM of 18 AND 12 =";LCM)
LCM(14,-6->LCM)
PRINT("LCM of 14 AND -6 =";LCM)
LCM(0,35->LCM)
PRINT("LCM of 0 AND 35 =";LCM)
END PROGRAM
- Output:
LCM of 18 and 12 = 36 LCM of 14 and -6 = 42 LCM of 0 and 35 = 0
Euler
Note % is integer division in Euler, not the mod operator.
begin new gcd; new lcm; gcd <- ` formal a; formal b; if b = 0 then a else gcd( b, a mod abs b ) ' ; lcm <- ` formal a; formal b; abs [ a * b ] % gcd( a, b ) ' ; out lcm( 15, 20 ) end $
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
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
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) = ", மீபொம(அ, ஆ)
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)
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 .
Fermat
Func Lecm(a,b)=|a|*|b|/GCD(a,b).
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 */ ;
Fortran
This solution is written as a combination of 2 functions, but a subroutine implementation would work great as well.
integer function lcm(a,b)
integer:: a,b
lcm = a*b / gcd(a,b)
end function lcm
integer function gcd(a,b)
integer :: a,b,t
do while (b/=0)
t = b
b = mod(a,b)
a = t
end do
gcd = abs(a)
end function gcd
FreeBASIC
Iterative solution
' FB 1.05.0 Win64
Function lcm (m As Integer, n As Integer) As Integer
If m = 0 OrElse n = 0 Then Return 0
If m < n Then Swap m, n '' to minimize iterations needed
Var count = 0
Do
count +=1
Loop Until (m * count) Mod n = 0
Return m * count
End Function
Print "lcm(12, 18) ="; lcm(12, 18)
Print "lcm(15, 12) ="; lcm(15, 12)
Print "lcm(10, 14) ="; lcm(10, 14)
Print
Print "Press any key to quit"
Sleep
- Output:
lcm(12, 18) = 36 lcm(15, 12) = 60 lcm(10, 14) = 70
Recursive solution
Reuses code from Greatest_common_divisor#Recursive_solution and correctly handles negative arguments
function gcdp( a as uinteger, b as uinteger ) as uinteger
if b = 0 then return a
return gcdp( b, a mod b )
end function
function gcd(a as integer, b as integer) as uinteger
return gcdp( abs(a), abs(b) )
end function
function lcm(a as integer, b as integer) as uinteger
return abs(a*b)/gcd(a,b)
end function
print "lcm( 12, -18) = "; lcm(12, -18)
print "lcm( 15, 12) = "; lcm(15, 12)
print "lcm(-10, -14) = "; lcm(-10, -14)
print "lcm( 0, 1) = "; lcm(0,1)
- Output:
lcm( 12, -18) = 36 lcm( 15, 12) = 60 lcm(-10, -14) = 70 lcm( 0, 1) = 0
Frink
Frink has a built-in LCM function that handles arbitrarily-large integers.
println[lcm[2562047788015215500854906332309589561, 6795454494268282920431565661684282819]]
FunL
FunL has function lcm
in module integers
with the following definition:
def
lcm( _, 0 ) = 0
lcm( 0, _ ) = 0
lcm( x, y ) = abs( (x\gcd(x, y)) y )
GAP
# Built-in
LcmInt(12, 18);
# 36
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
Groovy
def gcd
gcd = { m, n -> m = m.abs(); n = n.abs(); n == 0 ? m : m%n == 0 ? n : gcd(n, m % n) }
def lcd = { m, n -> Math.abs(m * n) / gcd(m, n) }
[[m: 12, n: 18, l: 36],
[m: -6, n: 14, l: 42],
[m: 35, n: 0, l: 0]].each { t ->
println "LCD of $t.m, $t.n is $t.l"
assert lcd(t.m, t.n) == t.l
}
- Output:
LCD of 12, 18 is 36 LCD of -6, 14 is 42 LCD of 35, 0 is 0
GW-BASIC
10 PRINT "LCM(35, 21) = ";
20 LET MLCM = 35
30 LET NLCM = 21
40 GOSUB 200: ' Calculate LCM
50 PRINT LCM
60 END
195 ' Calculate LCM
200 LET MGCD = MLCM
210 LET NGCD = NLCM
220 GOSUB 400: ' Calculate GCD
230 LET LCM = MLCM / GCD * NLCM
240 RETURN
395 ' Calculate GCD
400 WHILE MGCD <> 0
410 LET TMP = MGCD
420 LET MGCD = NGCD MOD MGCD
430 LET NGCD = TMP
440 WEND
450 LET GCD = NGCD
460 RETURN
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)
Icon and Unicon
The lcm routine from the Icon Programming Library uses gcd. The routine is
numbers provides lcm and gcd and looks like this:
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 truth valued arguments (0 and 1) it is equivalent to "and"
0 0 0 1
*./~ 0 1
0 0
0 1
Note: least common multiple is the original boolean multiplication. Constraining the universe of values to 0 and 1 allows us to additionally define logical negation (and boolean algebra was redefined to include this constraint in the early 1900s - the original concept of boolean algebra is now known as a boolean ring (though, talking to some people: there's been some linguistic drift even there)).
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);
}
}
JavaScript
ES5
Computing the least common multiple of an integer array, using the associative law:
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
*/
ES6
(() => {
'use strict';
// gcd :: Integral a => a -> a -> a
let gcd = (x, y) => {
let _gcd = (a, b) => (b === 0 ? a : _gcd(b, a % b)),
abs = Math.abs;
return _gcd(abs(x), abs(y));
}
// lcm :: Integral a => a -> a -> a
let lcm = (x, y) =>
x === 0 || y === 0 ? 0 : Math.abs(Math.floor(x / gcd(x, y)) * y);
// TEST
return lcm(12, 18);
})();
- Output:
36
jq
Direct method
# Define the helper function to take advantage of jq's tail-recursion optimization
def lcm(m; n):
def _lcm:
# state is [m, n, i]
if (.[2] % .[1]) == 0 then .[2] else (.[0:2] + [.[2] + m]) | _lcm end;
[m, n, m] | _lcm;
Julia
Built-in function:
lcm(m,n)
K
K3
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
K6
abs:|/-:\
gcd:{$[~x;y;o[x!y;x]]}
lcm:{abs[`i$x*y%gcd[x;y]]}
lcm .'(12 18; -6 14; 35 0)
36 42 0
lcm/1+!20
232792560
Klingphix
:gcd { u v -- n }
abs int swap abs int swap
[over over mod rot drop]
[dup]
while
drop
;
:lcm { m n -- n }
over over gcd rot swap div mult
;
12 18 lcm print nl { 36 }
"End " input
Kotlin
fun main(args: Array<String>) {
fun gcd(a: Long, b: Long): Long = if (b == 0L) a else gcd(b, a % b)
fun lcm(a: Long, b: Long): Long = a / gcd(a, b) * b
println(lcm(15, 9))
}
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
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
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
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
Demo code:
print lcm 38 46
Output:
874
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) )
m4
This should work with any POSIX-compliant m4. I have tested it with OpenBSD m4, GNU m4, and Heirloom Devtools m4.
divert(-1)
define(`gcd',
`ifelse(eval(`0 <= (' $1 `)'),`0',`gcd(eval(`-(' $1 `)'),eval(`(' $2 `)'))',
eval(`0 <= (' $2 `)'),`0',`gcd(eval(`(' $1 `)'),eval(`-(' $2 `)'))',
eval(`(' $1 `) == 0'),`0',`gcd(eval(`(' $2 `) % (' $1 `)'),eval(`(' $1 `)'))',
eval(`(' $2 `)'))')
define(`lcm',
`ifelse(eval(`0 <= (' $1 `)'),`0',`lcm(eval(`-(' $1 `)'),eval(`(' $2 `)'))',
eval(`0 <= (' $2 `)'),`0',`lcm(eval(`(' $1 `)'),eval(`-(' $2 `)'))',
eval(`(' $1 `) == 0'),`0',`eval(`(' $1 `) * (' $2 `) /' gcd(eval(`(' $1 `)'),eval(`(' $2 `)')))')')
divert`'dnl
dnl
lcm(-6, 14) = 42
lcm(2, 0) = 0
lcm(12, 18) = 36
lcm(12, 22) = 132
lcm(7, 31) = 217
- Output:
42 = 42 0 = 0 36 = 36 132 = 132 217 = 217
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
Mathematica/Wolfram Language
LCM[18,12]
-> 36
MATLAB / Octave
lcm(a,b)
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))
Microsoft Small Basic
Textwindow.Write("LCM(35, 21) = ")
mlcm = 35
nlcm = 21
CalculateLCM()
TextWindow.WriteLine(lcm)
Sub CalculateLCM
mgcd = mlcm
ngcd = nlcm
CalculateGCD()
lcm = mlcm / gcd * nlcm
EndSub
Sub CalculateGCD
While mgcd <> 0
tmp = mgcd
mgcd = Math.Remainder(ngcd, mgcd)
ngcd = tmp
EndWhile
gcd = ngcd
EndSub
MiniScript
gcd = function(a, b)
while b
temp = b
b = a % b
a = temp
end while
return abs(a)
end function
lcm = function(a,b)
if not a and not b then return 0
return abs(a * b) / gcd(a, b)
end function
print lcm(18,12)
- Output:
36
MiniZinc
function var int: lcm(int: a2,int:b2) =
let {
int:a1 = max(a2,b2);
int:b1 = min(a2,b2);
array[0..a1,0..b1] of var int: gcd;
constraint forall(a in 0..a1)(
forall(b in 0..b1)(
gcd[a,b] ==
if (b == 0) then
a
else
gcd[b, a mod b]
endif
)
)
} in (a1*b1) div gcd[a1,b1];
var int: lcm1 = lcm(18,12);
solve satisfy;
output [show(lcm1),"\n"];
- Output:
36
min
((0 <) (-1 *) when) :abs
((dup 0 ==) (pop abs) (swap over mod) () linrec) :gcd
(over over gcd '* dip div) :lcm
МК-61/52
ИПA ИПB * |x| ПC ИПA ИПB / [x] П9
ИПA ИПB ПA ИП9 * - ПB x=0 05 ИПC
ИПA / С/П
ML
mLite
fun gcd (a, 0) = a
| (0, b) = b
| (a, b) where (a < b)
= gcd (a, b rem a)
| (a, b) = gcd (b, a rem b)
fun lcm (a, b) = let val d = gcd (a, b)
in a * b div d
end
Modula-2
MODULE LeastCommonMultiple;
FROM STextIO IMPORT
WriteString, WriteLn;
FROM SWholeIO IMPORT
WriteInt;
PROCEDURE GCD(M, N: INTEGER): INTEGER;
VAR
Tmp: INTEGER;
BEGIN
WHILE M <> 0 DO
Tmp := M;
M := N MOD M;
N := Tmp;
END;
RETURN N;
END GCD;
PROCEDURE LCM(M, N: INTEGER): INTEGER;
BEGIN
RETURN M / GCD(M, N) * N;
END LCM;
BEGIN
WriteString("LCM(35, 21) = ");
WriteInt(LCM(35, 21), 1);
WriteLn;
END LeastCommonMultiple.
Nanoquery
def gcd(a, b)
if (a < 1) or (b < 1)
throw new(InvalidNumberException, "gcd cannot be calculated on values < 1")
end
c = 0
while b != 0
c = a
a = b
b = c % b
end
return a
end
def lcm(m, n)
return (m * n) / gcd(m, n)
end
println lcm(12, 18)
println lcm(6, 14)
println lcm(1,2) = lcm(2,1)
- Output:
36 42 true
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
Nim
The standard module "math" provides a function "lcm" for two integers and for an open array of integers. If we absolutely want to compute the least common multiple with our own procedure, it can be done this way (less efficient than the function in the standard library which avoids the modulo):
proc gcd(u, v: int): auto =
var
u = u
v = v
while v != 0:
u = u %% v
swap u, v
abs(u)
proc lcm(a, b: int): auto = abs(a * b) div gcd(a, b)
echo lcm(12, 18)
echo lcm(-6, 14)
- Output:
36 42
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;
}
}
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)
Oforth
lcm is already defined into Integer class :
12 18 lcm
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
Order
#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
PARI/GP
Built-in function:
lcm
Pascal
Program LeastCommonMultiple(output);
{$IFDEF FPC}
{$MODE DELPHI}
{$ENDIF}
function lcm(a, b: longint): longint;
begin
result := a;
while (result mod b) <> 0 do
inc(result, 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
PascalABC.NET
function GCD(a,b: integer): integer;
begin
while b > 0 do
(a,b) := (b,a mod b);
Result := a;
end;
function LCM(a,b: integer): integer := a = 0 ? 0 : a div GCD(a,b) * b;
begin
Println(LCM(12,18));
end.
- Output:
36
Perl
Using GCD:
sub gcd {
my ($x, $y) = @_;
while ($x) { ($x, $y) = ($y % $x, $x) }
$y
}
sub lcm {
my ($x, $y) = @_;
($x && $y) and $x / gcd($x, $y) * $y 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 ($f, $s) = @_;
while ($f != $s) {
($f, $s, $x, $y) = ($s, $f, $y, $x) if $f > $s;
$f = $s / $x * $x;
$f += $x if $f < $s;
}
$f
}
print lcm(1001, 221);
Phix
It is a builtin function, defined in builtins\gcd.e and accepting either two numbers or a single sequence of any length.
with javascript_semantics ?lcm(12,18) ?lcm({12,18})
- Output:
36 36
Phixmonti
def gcd /# u v -- n #/
abs int swap abs int swap
dup
while
over over mod rot drop dup
endwhile
drop
enddef
def lcm /# m n -- n #/
over over gcd rot swap / *
enddef
12345 50 lcm print
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;
}
Picat
Picat has a built-in function gcd/2
.
Function
lcm(X,Y)= abs(X*Y)//gcd(X,Y).
Predicate
lcm(X,Y,LCM) => LCM = abs(X*Y)//gcd(X,Y).
Functional (fold/3)
lcm(List) = fold(lcm,1,List).
Test
go =>
L = [
[12,18],
[-6,14],
[35,0],
[7,10],
[2562047788015215500854906332309589561,6795454494268282920431565661684282819]
],
foreach([X,Y] in L)
println((X,Y)=lcm(X,Y))
end,
println('1..20'=lcm(1..20)),
println('1..50'=lcm(1..50)),
nl.
- Output:
(12,18) = 36 (-6,14) = 42 (35,0) = 0 (7,10) = 70 (2562047788015215500854906332309589561,6795454494268282920431565661684282819) = 15669251240038298262232125175172002594731206081193527869 1..20 = 232792560 1..50 = 3099044504245996706400
PicoLisp
Using 'gcd' from Greatest common divisor#PicoLisp:
(de lcm (A B)
(abs (*/ A B (gcd A B))) )
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
PowerShell
version 1
function gcd ($a, $b) {
function pgcd ($n, $m) {
if($n -le $m) {
if($n -eq 0) {$m}
else{pgcd $n ($m-$n)}
}
else {pgcd $m $n}
}
$n = [Math]::Abs($a)
$m = [Math]::Abs($b)
(pgcd $n $m)
}
function lcm ($a, $b) {
[Math]::Abs($a*$b)/(gcd $a $b)
}
lcm 12 18
version 2
version2 is faster than version1
function gcd ($a, $b) {
function pgcd ($n, $m) {
if($n -le $m) {
if($n -eq 0) {$m}
else{pgcd $n ($m%$n)}
}
else {pgcd $m $n}
}
$n = [Math]::Abs($a)
$m = [Math]::Abs($b)
(pgcd $n $m)
}
function lcm ($a, $b) {
[Math]::Abs($a*$b)/(gcd $a $b)
}
lcm 12 18
Output:
36
Prolog
SWI-Prolog knows gcd.
lcm(X, Y, Z) :-
Z is abs(X * Y) / gcd(X,Y).
Example:
?- lcm(18,12, Z). Z = 36.
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
Python
Functional
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
>>>
Or, for compositional flexibility, a curried lcm, expressed in terms of our own gcd function:
'''Least common multiple'''
from inspect import signature
# lcm :: Int -> Int -> Int
def lcm(x):
'''The smallest positive integer divisible
without remainder by both x and y.
'''
return lambda y: 0 if 0 in (x, y) else abs(
y * (x // gcd_(x)(y))
)
# gcd_ :: Int -> Int -> Int
def gcd_(x):
'''The greatest common divisor in terms of
the divisibility preordering.
'''
def go(a, b):
return go(b, a % b) if 0 != b else a
return lambda y: go(abs(x), abs(y))
# TEST ----------------------------------------------------
# main :: IO ()
def main():
'''Tests'''
print(
fTable(
__doc__ + 's of 60 and [12..20]:'
)(repr)(repr)(
lcm(60)
)(enumFromTo(12)(20))
)
pairs = [(0, 2), (2, 0), (-6, 14), (12, 18)]
print(
fTable(
'\n\n' + __doc__ + 's of ' + repr(pairs) + ':'
)(repr)(repr)(
uncurry(lcm)
)(pairs)
)
# GENERIC -------------------------------------------------
# enumFromTo :: (Int, Int) -> [Int]
def enumFromTo(m):
'''Integer enumeration from m to n.'''
return lambda n: list(range(m, 1 + n))
# uncurry :: (a -> b -> c) -> ((a, b) -> c)
def uncurry(f):
'''A function over a tuple, derived from
a vanilla or curried function.
'''
if 1 < len(signature(f).parameters):
return lambda xy: f(*xy)
else:
return lambda xy: f(xy[0])(xy[1])
# unlines :: [String] -> String
def unlines(xs):
'''A single string derived by the intercalation
of a list of strings with the newline character.
'''
return '\n'.join(xs)
# FORMATTING ----------------------------------------------
# fTable :: String -> (a -> String) ->
# (b -> String) -> (a -> b) -> [a] -> String
def fTable(s):
'''Heading -> x display function -> fx display function ->
f -> xs -> tabular string.
'''
def go(xShow, fxShow, f, xs):
ys = [xShow(x) for x in xs]
w = max(map(len, ys))
return s + '\n' + '\n'.join(map(
lambda x, y: y.rjust(w, ' ') + ' -> ' + fxShow(f(x)),
xs, ys
))
return lambda xShow: lambda fxShow: lambda f: lambda xs: go(
xShow, fxShow, f, xs
)
# MAIN ---
if __name__ == '__main__':
main()
- Output:
Least common multiples of 60 and [12..20]: 12 -> 60 13 -> 780 14 -> 420 15 -> 60 16 -> 240 17 -> 1020 18 -> 180 19 -> 1140 20 -> 60 Least common multiples of [(0, 2), (2, 0), (-6, 14), (12, 18)]: (0, 2) -> 0 (2, 0) -> 0 (-6, 14) -> 42 (12, 18) -> 36
Procedural
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
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
>>>
Repeated modulo
>>> 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
>>>
Qi
(define gcd
A 0 -> A
A B -> (gcd B (MOD A B)))
(define lcm A B -> (/ (* A B) (gcd A B)))
Quackery
[ [ dup while
tuck mod again ]
drop abs ] is gcd ( n n --> n )
[ 2dup and iff
[ 2dup gcd
/ * abs ]
else and ] is lcm ( n n --> n )
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)
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
Raku
(formerly 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
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 / ;
REXX
version 1
The lcm subroutine can handle any number of integers and/or arguments.
The integers (negative/zero/positive) can be (as per the numeric digits) up to ten thousand digits.
Usage note: the integers can be expressed as a list and/or specified as individual arguments (or as mixed).
/*REXX program finds the LCM (Least Common Multiple) of any number of integers. */
numeric digits 10000 /*can handle 10k decimal digit numbers.*/
say 'the LCM of 19 and 0 is ───► ' lcm(19 0 )
say 'the LCM of 0 and 85 is ───► ' lcm( 0 85 )
say 'the LCM of 14 and -6 is ───► ' lcm(14, -6 )
say 'the LCM of 18 and 12 is ───► ' lcm(18 12 )
say 'the LCM of 18 and 12 and -5 is ───► ' lcm(18 12, -5 )
say 'the LCM of 18 and 12 and -5 and 97 is ───► ' lcm(18, 12, -5, 97)
say 'the LCM of 2**19-1 and 2**521-1 is ───► ' lcm(2**19-1 2**521-1)
/* [↑] 7th & 13th Mersenne primes.*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
lcm: procedure; parse arg $,_; $=$ _; do i=3 to arg(); $=$ arg(i); end /*i*/
parse var $ x $ /*obtain the first value in args. */
x=abs(x) /*use the absolute value of X. */
do while $\=='' /*process the remainder of args. */
parse var $ ! $; if !<0 then !=-! /*pick off the next arg (ABS val).*/
if !==0 then return 0 /*if zero, then LCM is also zero. */
d=x*! /*calculate part of the LCM here. */
do until !==0; parse value x//! ! with ! x
end /*until*/ /* [↑] this is a short & fast GCD*/
x=d%x /*divide the pre─calculated value.*/
end /*while*/ /* [↑] process subsequent args. */
return x /*return with the LCM of the args.*/
output when using the (internal) supplied list:
the LCM of 19 and 0 is ───► 0 the LCM of 0 and 85 is ───► 0 the LCM of 14 and -6 is ───► 42 the LCM of 18 and 12 is ───► 36 the LCM of 18 and 12 and -5 is ───► 180 the LCM of 18 and 12 and -5 and 97 is ───► 17460 the LCM of 2**19-1 and 2**521-1 is ───► 3599124170836896975638715824247986405702540425206233163175195063626010878994006898599180426323472024265381751210505324617708575722407440034562999570663839968526337
version 2
using different argument handling-
Use as lcm(a,b,c,---)
lcm2: procedure
x=abs(arg(1))
do k=2 to arg() While x<>0
y=abs(arg(k))
x=x*y/gcd2(x,y)
end
return x
gcd2: procedure
x=abs(arg(1))
do j=2 to arg()
y=abs(arg(j))
If y<>0 Then Do
do until z==0
z=x//y
x=y
y=z
end
end
end
return x
Ring
see lcm(24,36)
func lcm m,n
lcm = m*n / gcd(m,n)
return lcm
func gcd gcd, b
while b
c = gcd
gcd = b
b = c % b
end
return gcd
RPL
For unsigned integers
≪ DUP2 < ≪ SWAP ≫ IFT WHILE DUP B→R REPEAT SWAP OVER / LAST ROT * - END DROP ≫ 'GCD' STO ≪ DUP2 * ROT ROT GCD / ≫ 'LCM' STO #12d #18d LCM
- Output:
1: #36d
For usual integers (floating point without decimal part)
≪ WHILE DUP REPEAT SWAP OVER MOD END DROP ABS ≫ 'GCD' STO ≪ DUP2 * ROT ROT GCD / ≫ 'LCM' STO
Ruby
Ruby has an Integer#lcm method, which finds the least common multiple of two integers.
irb(main):001:0> 12.lcm 18
=> 36
I can also write my own lcm method. This one takes any number of arguments.
def gcd(m, n)
m, n = n, m % n until n.zero?
m.abs
end
def lcm(*args)
args.inject(1) do |m, n|
return 0 if n.zero?
(m * n).abs / gcd(m, n)
end
end
p lcm 12, 18, 22
p lcm 15, 14, -6, 10, 21
- Output:
396 210
Run BASIC
print "lcm( 12, -18) = "; lcm( 12, -18)
print "lcm( 15, 12) = "; lcm( 15, 12)
print "lcm(-10, -14) = "; lcm(-10, -14)
print "lcm( 0, 1) = "; lcm( 0, 1)
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
Rust
This implementation uses a recursive implementation of Stein's algorithm to calculate the gcd.
use std::cmp::{max, min};
fn gcd(a: usize, b: usize) -> usize {
match ((a, b), (a & 1, b & 1)) {
((x, y), _) if x == y => y,
((0, x), _) | ((x, 0), _) => x,
((x, y), (0, 1)) | ((y, x), (1, 0)) => gcd(x >> 1, y),
((x, y), (0, 0)) => gcd(x >> 1, y >> 1) << 1,
((x, y), (1, 1)) => {
let (x, y) = (min(x, y), max(x, y));
gcd((y - x) >> 1, x)
}
_ => unreachable!(),
}
}
fn lcm(a: usize, b: usize) -> usize {
a * b / gcd(a, b)
}
fn main() {
println!("{}", lcm(6324, 234))
}
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
Scheme
>(define gcd (lambda (a b)
(if (zero? b)
a
(gcd b (remainder a b)))))
>(define lcm (lambda (a b)
(if (or (zero? a) (zero? b))
0
(abs (* b (floor (/ a (gcd a b))))))))
>(lcm 12 18)
36
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]
SenseTalk
function gcd m, n
repeat while m is greater than 0
put m into temp
put n modulo m into m
put temp into n
end repeat
return n
end gcd
function lcm m, n
return m divided by gcd(m, n) times n
end lcm
Sidef
Built-in:
say Math.lcm(1001, 221)
Using GCD:
func gcd(a, b) {
while (a) { (a, b) = (b % a, a) }
return b
}
func lcm(a, b) {
(a && b) ? (a / gcd(a, b) * b) : 0
}
say lcm(1001, 221)
- Output:
17017
Smalltalk
Smalltalk has a built-in lcm
method on SmallInteger
:
12 lcm: 18
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);
}
Standard ML
Readable version
fun gcd (0,n) = n
| gcd (m,n) = gcd(n mod m, m)
fun lcm (m,n) = abs(x * y) div gcd (m, n)
Alternate version
val rec gcd = fn (x, 0) => abs x | p as (_, y) => gcd (y, Int.rem p)
val lcm = fn p as (x, y) => Int.quot (abs (x * y), gcd p)
Swift
Using the Swift GCD function.
func lcm(a:Int, b:Int) -> Int {
return abs(a * b) / gcd_rec(a, b)
}
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
TI-83 BASIC
lcm(12,18
36
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
TXR
$ txr -p '(lcm (expt 2 123) (expt 6 49) 17)'
43259338018880832376582582128138484281161556655442781051813888
TypeScript
// Least common multiple
function gcd(m: number, n: number): number {
var tmp: number;
while (m != 0) {
tmp = m;
m = n % m;
n = tmp;
}
return n;
}
function lcm(m: number, n: number): number {
return Math.floor(m / gcd(m, n)) * n;
}
console.log(`LCM(35, 21) = ${lcm(35, 21)}`);
- Output:
LCM(35, 21) = 105
uBasic/4tH
Print "LCM of 12 : 18 = "; FUNC(_LCM(12,18))
End
_GCD_Iterative_Euclid Param(2)
Local (1)
Do While b@
c@ = a@
a@ = b@
b@ = c@ % b@
Loop
Return (ABS(a@))
_LCM Param(2)
If a@*b@
Return (ABS(a@*b@)/FUNC(_GCD_Iterative_Euclid(a@,b@)))
Else
Return (0)
EndIf
- Output:
LCM of 12 : 18 = 36 0 OK, 0:330
Uiua
# Greatest Common Divisor using Euclidean algorithm
Gcd ← ⊙◌⍢(⟜◿:|±,)
# Least Common Multiple
Lcm ← ÷⊃(Gcd|⌵×)
UNIX 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
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
Ursa
import "math"
out (lcm 12 18) endl console
- Output:
36
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));
}
VBA
Function gcd(u As Long, v As Long) As Long
Dim t As Long
Do While v
t = u
u = v
v = t Mod v
Loop
gcd = u
End Function
Function lcm(m As Long, n As Long) As Long
lcm = Abs(m * n) / gcd(m, n)
End Function
VBScript
Function LCM(a,b)
LCM = POS((a * b)/GCD(a,b))
End Function
Function GCD(a,b)
Do
If a Mod b > 0 Then
c = a Mod b
a = b
b = c
Else
GCD = b
Exit Do
End If
Loop
End Function
Function POS(n)
If n < 0 Then
POS = n * -1
Else
POS = n
End If
End Function
i = WScript.Arguments(0)
j = WScript.Arguments(1)
WScript.StdOut.Write "The LCM of " & i & " and " & j & " is " & LCM(i,j) & "."
WScript.StdOut.WriteLine
- Output:
C:\>cscript /nologo lcm.vbs 12 18 The LCM of 12 and 18 is 36. C:\>cscript /nologo lcm.vbs 14 -6 The LCM of 14 and -6 is 42. C:\>cscript /nologo lcm.vbs 0 35 The LCM of 0 and 35 is 0. C:\>
Wortel
Operator
@lcm a b
Number expression
!#~km a b
Function (using gcd)
&[a b] *b /a @gcd a b
Wren
var gcd = Fn.new { |x, y|
while (y != 0) {
var t = y
y = x % y
x = t
}
return x.abs
}
var lcm = Fn.new { |x, y|
if (x == 0 && y == 0) return 0
return (x*y).abs / gcd.call(x, y)
}
var xys = [[12, 18], [-6, 14], [35, 0]]
for (xy in xys) {
System.print("lcm(%(xy[0]), %(xy[1]))\t%("\b"*5) = %(lcm.call(xy[0], xy[1]))")
}
- Output:
lcm(12, 18) = 36 lcm(-6, 14) = 42 lcm(35, 0) = 0
XBasic
' Least common multiple
PROGRAM "leastcommonmultiple"
VERSION "0.0001"
DECLARE FUNCTION Entry()
INTERNAL FUNCTION Gcd(m&, n&)
INTERNAL FUNCTION Lcm(m&, n&)
FUNCTION Entry()
PRINT "LCM(35, 21) ="; Lcm(35, 21)
END FUNCTION
FUNCTION Gcd(m&, n&)
DO WHILE m& <> 0
tmp& = m&
m& = n& MOD m&
n& = tmp&
LOOP
RETURN n&
END FUNCTION
FUNCTION Lcm(m&, n&)
RETURN m& / Gcd(m&, n&) * n&
END FUNCTION
END PROGRAM
- Output:
LCM(35, 21) = 105
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)))
Yabasic
sub gcd(u, v)
local t
u = int(abs(u))
v = int(abs(v))
while(v)
t = u
u = v
v = mod(t, v)
wend
return u
end sub
sub lcm(m, n)
return m / gcd(m, n) * n
end sub
print "Least common multiple: ", lcm(12345, 23044)
zkl
fcn lcm(m,n){ (m*n).abs()/m.gcd(n) } // gcd is a number method
- Output:
zkl: lcm(12,18) 36 zkl: lcm(-6,14) 42 zkl: lcm(35,0) 0
- Recursion
- Programming Tasks
- Solutions by Programming Task
- 11l
- 360 Assembly
- 8th
- Action!
- Ada
- ALGOL 68
- ALGOL W
- APL
- AppleScript
- Arendelle
- Arturo
- Assembly
- X86 Assembly
- ATS
- AutoHotkey
- AutoIt
- AWK
- BASIC
- Applesoft BASIC
- BBC BASIC
- IS-BASIC
- Tiny BASIC
- BASIC256
- Batch File
- Bc
- BCPL
- Befunge
- BQN
- Bracmat
- Brat
- Bruijn
- C
- C sharp
- C++
- Boost
- Clojure
- CLU
- COBOL
- Common Lisp
- Cowgol
- D
- Dart
- Delphi
- DWScript
- Draco
- EasyLang
- EchoLisp
- Elena
- Elixir
- Erlang
- ERRE
- Euler
- Euphoria
- Excel
- Ezhil
- F Sharp
- Factor
- Fermat
- Forth
- Fortran
- FreeBASIC
- Frink
- FunL
- GAP
- Go
- Groovy
- GW-BASIC
- Haskell
- Icon
- Unicon
- Icon Programming Library
- J
- Java
- JavaScript
- Jq
- Julia
- K
- Klingphix
- Kotlin
- LabVIEW
- Lasso
- Liberty BASIC
- Logo
- Lua
- M4
- Maple
- Mathematica
- Wolfram Language
- MATLAB
- Octave
- Maxima
- Microsoft Small Basic
- MiniScript
- MiniZinc
- Min
- МК-61/52
- ML
- MLite
- Modula-2
- Nanoquery
- NetRexx
- Nim
- Objeck
- OCaml
- Oforth
- OoRexx
- Order
- PARI/GP
- Pascal
- PascalABC.NET
- Perl
- Phix
- Phixmonti
- PHP
- Picat
- PicoLisp
- PL/I
- PowerShell
- Prolog
- PureBasic
- Python
- Qi
- Quackery
- R
- Racket
- Raku
- Retro
- REXX
- Ring
- RPL
- Ruby
- Run BASIC
- Rust
- Scala
- Scheme
- Seed7
- SenseTalk
- Sidef
- Smalltalk
- Sparkling
- Standard ML
- Swift
- Tcl
- TI-83 BASIC
- TSE SAL
- TXR
- TypeScript
- UBasic/4tH
- Uiua
- UNIX Shell
- C Shell
- Ursa
- Vala
- VBA
- VBScript
- Wortel
- Wren
- XBasic
- XPL0
- Yabasic
- Zkl
- Pages with too many expensive parser function calls