Least common multiple: Difference between revisions
→{{header|TXR}}: Added. |
m →{{header|TXR}}: Typo. |
||
Line 2,207:
=={{header|TXR}}==
<lang bash>$ txr -p '(lcm (expt 2 123) (expt 6 49) 17)'
|
Revision as of 14:32, 21 June 2017
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
Compute the least common multiple of two integers.
Given m and n, the least common multiple is the smallest positive integer that has both m and n as factors.
- 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.
- References
8th
<lang forth>
- 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</lang>
- Output:
LCM of 18 and 12 = 36 LCM of 14 and -6 = 42 LCM of 0 and 35 = 0
Ada
lcm_test.adb: <lang Ada>with Ada.Text_IO; use Ada.Text_IO;
procedure Lcm_Test is
function Gcd (A, B : Integer) return Integer is M : Integer := A; N : Integer := B; T : Integer; begin while N /= 0 loop T := M; M := N; N := T mod N; end loop; return M; end Gcd;
function Lcm (A, B : Integer) return Integer is begin if A = 0 or B = 0 then return 0; end if; return abs (A) * (abs (B) / Gcd (A, B)); end Lcm;
begin
Put_Line ("LCM of 12, 18 is" & Integer'Image (Lcm (12, 18))); Put_Line ("LCM of -6, 14 is" & Integer'Image (Lcm (-6, 14))); Put_Line ("LCM of 35, 0 is" & Integer'Image (Lcm (35, 0)));
end Lcm_Test;</lang>
Output:
LCM of 12, 18 is 36 LCM of -6, 14 is 42 LCM of 35, 0 is 0
ALGOL 68
<lang algol68> 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 </lang>
- 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
<lang algolw>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.</lang>
APL
APL provides this function. <lang apl> 12^18 36</lang> 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: <lang apl> LCM←{(|⍺×⍵)÷⍺∨⍵}
12 LCM 18
36</lang>
AppleScript
<lang AppleScript>-- lcm :: Integral a => a -> a -> a on lcm(x, y)
if x = 0 or y = 0 then 0 else abs(x div (gcd(x, y)) * y) end if
end lcm
-- TEST
on run
lcm(12, 18) --> 36
end run
-- GENERAL FUNCTIONS
-- abs :: Num a => a -> a on abs(x)
if x < 0 then -x else x end if
end abs
-- gcd :: Integral a => a -> a -> a on gcd(x, y)
script _gcd on lambda(a, b) if b = 0 then a else lambda(b, a mod b) end if end lambda end script _gcd's lambda(abs(x), abs(y))
end gcd</lang>
- Output:
<lang AppleScript>36</lang>
Arendelle
For GCD function check out here
< a , b > ( return , abs ( @a * @b ) / !gcd( @a , @b ) )
Assembly
x86 Assembly
<lang asm>
- 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
</lang>
AutoHotkey
<lang autohotkey>LCM(Number1,Number2) {
If (Number1 = 0 || Number2 = 0) Return Var := Number1 * Number2 While, Number2 Num := Number2, Number2 := Mod(Number1,Number2), Number1 := Num Return, Var // Number1
}
Num1 = 12 Num2 = 18 MsgBox % LCM(Num1,Num2)</lang>
AutoIt
<lang AutoIt> Func _LCM($a, $b) Local $c, $f, $m = $a, $n = $b $c = 1 While $c <> 0 $f = Int($a / $b) $c = $a - $b * $f If $c <> 0 Then $a = $b $b = $c EndIf WEnd Return $m * $n / $b EndFunc ;==>_LCM </lang> Example <lang AutoIt> ConsoleWrite(_LCM(12,18) & @LF) ConsoleWrite(_LCM(-5,12) & @LF) ConsoleWrite(_LCM(13,0) & @LF) </lang>
36 60 0
--BugFix (talk) 14:32, 15 November 2013 (UTC)
AWK
<lang awk># greatest common divisor function gcd(m, n, t) { # Euclid's method while (n != 0) { t = m m = n n = t % n } return m }
- least common multiple
function lcm(m, n, r) { if (m == 0 || n == 0) return 0 r = m * n / gcd(m, n) return r < 0 ? -r : r }
- Read two integers from each line of input.
- Print their least common multiple.
{ print lcm($1, $2) }</lang>
Example input and output:
$ awk -f lcd.awk 12 18 36 -6 14 42 35 0 0
BASIC
Applesoft BASIC
ported from BBC BASIC <lang ApplesoftBasic>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</lang>
BBC BASIC
<lang BBC BASIC>
DEF FN_LCM(M%,N%) IF M%=0 OR N%=0 THEN =0 ELSE =ABS(M%*N%)/FN_GCD_Iterative_Euclid(M%, N%) DEF FN_GCD_Iterative_Euclid(A%, B%) LOCAL C% WHILE B% C% = A% A% = B% B% = C% MOD B% ENDWHILE = ABS(A%)
</lang>
Batch File
<lang dos>@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</lang>
- Output:
LCM = 36
bc
<lang bc>/* greatest common divisor */ define g(m, n) { auto t
/* Euclid's method */ while (n != 0) { t = m m = n n = t % n } return (m) }
/* least common multiple */ define l(m, n) { auto r
if (m == 0 || n == 0) return (0) r = m * n / g(m, n) if (r < 0) return (-r) return (r) }</lang>
Bracmat
We utilize the fact that Bracmat simplifies fractions (using Euclid's algorithm). The function den$number
returns the denominator of a number.
<lang bracmat>(gcd=
a b
. !arg:(?a.?b)
& den$(!a*!b^-1) * (!a:<0&-1|1) * !a
); out$(gcd$(12.18) gcd$(-6.14) gcd$(35.0) gcd$(117.18))</lang> Output:
36 42 35 234
Brat
<lang 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 </lang>
C
<lang C>#include <stdio.h>
int gcd(int m, int n) {
int tmp; while(m) { tmp = m; m = n % m; n = tmp; } return n;
}
int lcm(int m, int n) {
return m / gcd(m, n) * n;
}
int main() {
printf("lcm(35, 21) = %d\n", lcm(21,35)); return 0;
}</lang>
C++
<lang cpp>#include <boost/math/common_factor.hpp>
- include <iostream>
int main( ) {
std::cout << "The least common multiple of 12 and 18 is " << boost::math::lcm( 12 , 18 ) << " ,\n" << "and the greatest common divisor " << boost::math::gcd( 12 , 18 ) << " !" << std::endl ; return 0 ;
}</lang>
- Output:
The least common multiple of 12 and 18 is 36 , and the greatest common divisor 6 !
Alternate solution
<lang cpp>
- include <cstdlib>
- include <iostream>
- include <tuple>
using namespace std;
int gcd(int a, int b) {
a = abs(a); b = abs(b); while (b != 0) { tie(a, b) = 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() {
cout << "The least common multiple of 12 and 18 is " << lcm(12, 18) << " ,\n" << "and the greatest common divisor " << gcd(12, 18) << " !" << endl; return 0;
} </lang>
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>
- Output:
lcm(12,18)=36
Clojure
<lang Clojure>(defn gcd
[a b] (if (zero? b) a (recur b, (mod a b))))
(defn lcm
[a b] (/ (* a b) (gcd a b)))
- to calculate the lcm for a variable number of arguments
(defn lcmv [& v] (reduce lcm v)) </lang>
COBOL
<lang cobol> IDENTIFICATION DIVISION.
PROGRAM-ID. show-lcm.
ENVIRONMENT DIVISION. CONFIGURATION SECTION. REPOSITORY. FUNCTION lcm . PROCEDURE DIVISION. DISPLAY "lcm(35, 21) = " FUNCTION lcm(35, 21) GOBACK . END PROGRAM show-lcm.
IDENTIFICATION DIVISION. FUNCTION-ID. lcm. ENVIRONMENT DIVISION. CONFIGURATION SECTION. REPOSITORY. FUNCTION gcd . DATA DIVISION. LINKAGE SECTION. 01 m PIC S9(8). 01 n PIC S9(8). 01 ret PIC S9(8).
PROCEDURE DIVISION USING VALUE m, n RETURNING ret. COMPUTE ret = FUNCTION ABS(m * n) / FUNCTION gcd(m, n) GOBACK . END FUNCTION lcm. IDENTIFICATION DIVISION. FUNCTION-ID. gcd.
DATA DIVISION. LOCAL-STORAGE SECTION. 01 temp PIC S9(8).
01 x PIC S9(8). 01 y PIC S9(8).
LINKAGE SECTION. 01 m PIC S9(8). 01 n PIC S9(8). 01 ret PIC S9(8).
PROCEDURE DIVISION USING VALUE m, n RETURNING ret. MOVE m to x MOVE n to y
PERFORM UNTIL y = 0 MOVE x TO temp MOVE y TO x MOVE FUNCTION MOD(temp, y) TO Y END-PERFORM
MOVE FUNCTION ABS(x) TO ret GOBACK . END FUNCTION gcd.</lang>
Common Lisp
Common Lisp provides the lcm function. It can accept two or more (or less) parameters.
<lang lisp>CL-USER> (lcm 12 18) 36 CL-USER> (lcm 12 18 22) 396</lang>
Here is one way to reimplement it.
<lang lisp>CL-USER> (defun my-lcm (&rest args) (reduce (lambda (m n) (cond ((or (= m 0) (= n 0)) 0) (t (abs (/ (* m n) (gcd m n)))))) args :initial-value 1)) MY-LCM CL-USER> (my-lcm 12 18) 36 CL-USER> (my-lcm 12 18 22) 396</lang>
In this code, the lambda finds the least common multiple of two integers, and the reduce transforms it to accept any number of parameters. The reduce operation exploits how lcm is associative, (lcm a b c) == (lcm (lcm a b) c); and how 1 is an identity, (lcm 1 a) == a.
D
<lang d>import std.stdio, std.bigint, std.math;
T gcd(T)(T a, T b) pure nothrow {
while (b) { immutable t = b; b = a % b; a = t; } return a;
}
T lcm(T)(T m, T n) pure nothrow {
if (m == 0) return m; if (n == 0) return n; return abs((m * n) / gcd(m, n));
}
void main() {
lcm(12, 18).writeln; lcm("2562047788015215500854906332309589561".BigInt, "6795454494268282920431565661684282819".BigInt).writeln;
}</lang>
- Output:
36 15669251240038298262232125175172002594731206081193527869
DWScript
<lang delphi>PrintLn(Lcm(12, 18));</lang> Output:
36
Dart
<lang 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);
}
</lang>
EchoLisp
(lcm a b) is already here as a two arguments function. Use foldl to find the lcm of a list of numbers. <lang lisp> (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 </lang>
Elixir
<lang 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)</lang>
- Output:
60
Erlang
<lang erlang>% Implemented by Arjun Sunel -module(lcm). -export([main/0]).
main() -> lcm(-3,4).
gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).
lcm(A,B) -> abs(A*B div gcd(A,B)).</lang>
- Output:
12
ERRE
<lang 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</lang>
- Output:
LCM of 18 and 12 = 36 LCM of 14 and -6 = 42 LCM of 0 and 35 = 0
Euphoria
<lang euphoria>function gcd(integer m, integer n)
integer tmp while m do tmp = m m = remainder(n,m) n = tmp end while return n
end function
function lcm(integer m, integer n)
return m / gcd(m, n) * n
end function</lang>
Excel
Excel's LCM can handle multiple values. Type in a cell: <lang excel>=LCM(A1:J1)</lang> 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
<lang src="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) = ", மீபொம(அ, ஆ) </lang>
F#
<lang fsharp>let rec gcd x y = if y = 0 then abs x else gcd y (x % y)
let lcm x y = x * y / (gcd x y)</lang>
Factor
The vocabulary math.functions already provides lcm.
<lang factor>USING: math.functions prettyprint ; 26 28 lcm .</lang>
This program outputs 364.
One can also reimplement lcm.
<lang factor>USING: kernel math prettyprint ; IN: script
- gcd ( a b -- c )
[ abs ] [ [ nip ] [ mod ] 2bi gcd ] if-zero ;
- lcm ( a b -- c )
[ * abs ] [ gcd ] 2bi / ;
26 28 lcm .</lang>
Forth
<lang forth>: gcd ( a b -- n )
begin dup while tuck mod repeat drop ;
- lcm ( a b -- n )
over 0= over 0= or if 2drop 0 exit then 2dup gcd abs */ ;</lang>
Fortran
This solution is written as a combination of 2 functions, but a subroutine implementation would work great as well. <lang Fortran>
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
</lang>
FreeBASIC
<lang freebasic>' 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</lang>
- Output:
lcm(12, 18) = 36 lcm(15, 12) = 60 lcm(10, 14) = 70
Frink
Frink has a built-in LCM function that handles arbitrarily-large integers. <lang frink> println[lcm[2562047788015215500854906332309589561, 6795454494268282920431565661684282819]] </lang>
FunL
FunL has function lcm
in module integers
with the following definition:
<lang funl>def
lcm( _, 0 ) = 0 lcm( 0, _ ) = 0 lcm( x, y ) = abs( (x\gcd(x, y)) y )</lang>
GAP
<lang gap># Built-in LcmInt(12, 18);
- 36</lang>
Go
<lang go>package main
import (
"fmt" "math/big"
)
var m, n, z big.Int
func init() {
m.SetString("2562047788015215500854906332309589561", 10) n.SetString("6795454494268282920431565661684282819", 10)
}
func main() {
fmt.Println(z.Mul(z.Div(&m, z.GCD(nil, nil, &m, &n)), &n))
}</lang>
- Output:
15669251240038298262232125175172002594731206081193527869
Groovy
<lang 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
}</lang>
- Output:
LCD of 12, 18 is 36 LCD of -6, 14 is 42 LCD of 35, 0 is 0
Haskell
That is already available as the function lcm in the Prelude. Here's the implementation:
<lang haskell>lcm :: (Integral a) => a -> a -> a lcm _ 0 = 0 lcm 0 _ = 0 lcm x y = abs ((x `quot` (gcd x y)) * y)</lang>
Icon and Unicon
The lcm routine from the Icon Programming Library uses gcd. The routine is
<lang Icon>link numbers procedure main() write("lcm of 18, 36 = ",lcm(18,36)) write("lcm of 0, 9 36 = ",lcm(0,9)) end</lang>
numbers provides lcm and gcd and looks like this: <lang Icon>procedure lcm(i, j) #: least common multiple
if (i = 0) | (j = 0) then return 0 return abs(i * j) / gcd(i, j)
end</lang>
J
J provides the dyadic verb *.
which returns the least common multiple of its left and right arguments.
<lang j> 12 *. 18 36
12 *. 18 22
36 132
*./ 12 18 22
396
0 1 0 1 *. 0 0 1 1 NB. for truth valued arguments (0 and 1) it is equivalent to "and"
0 0 0 1
*./~ 0 1
0 0 0 1</lang>
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).
Java
<lang java>import java.util.Scanner;
public class LCM{
public static void main(String[] args){ Scanner aScanner = new Scanner(System.in); //prompts user for values to find the LCM for, then saves them to m and n System.out.print("Enter the value of m:"); int m = aScanner.nextInt(); System.out.print("Enter the value of n:"); int n = aScanner.nextInt(); int lcm = (n == m || n == 1) ? m :(m == 1 ? n : 0); /* this section increases the value of mm until it is greater / than or equal to nn, then does it again when the lesser / becomes the greater--if they aren't equal. If either value is 1, / no need to calculate*/ if (lcm == 0) { int mm = m, nn = n; while (mm != nn) { while (mm < nn) { mm += m; } while (nn < mm) { nn += n; } } lcm = mm; } System.out.println("lcm(" + m + ", " + n + ") = " + lcm); }
}</lang>
JavaScript
ES5
Computing the least common multiple of an integer array, using the associative law:
<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]); 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
- /</lang>
ES6
<lang JavaScript>(() => {
'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);
})();</lang>
- Output:
36
jq
Direct method <lang jq># 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; </lang>
Julia
Built-in function: <lang julia>lcm(m,n)</lang>
K
<lang K> gcd:{:[~x;y;_f[y;x!y]]}
lcm:{_abs _ x*y%gcd[x;y]}
lcm .'(12 18; -6 14; 35 0)
36 42 0
lcm/1+!20
232792560</lang>
Kotlin
<lang scala>fun main(args: Array<String>) {
fun gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b) fun lcm(a: Int, b: Int) = a * b / gcd(a, b) println(lcm(15, 9))
} </lang>
LabVIEW
Requires GCD. This image is a VI Snippet, an executable image of LabVIEW code. The LabVIEW version is shown on the top-right hand corner. You can download it, then drag-and-drop it onto the LabVIEW block diagram from a file browser, and it will appear as runnable, editable code.
Lasso
<lang Lasso>define gcd(a,b) => { while(#b != 0) => { local(t = #b) #b = #a % #b #a = #t } return #a } define lcm(m,n) => { #m == 0 || #n == 0 ? return 0 local(r = (#m * #n) / decimal(gcd(#m, #n))) return integer(#r)->abs }
lcm(-6, 14) lcm(2, 0) lcm(12, 18) lcm(12, 22) lcm(7, 31)</lang>
- Output:
42 0 36 132 217
Liberty BASIC
<lang lb>print "Least Common Multiple of 12 and 18 is ";LCM(12,18) end
function LCM(m,n)
LCM=abs(m*n)/GCD(m,n) end function
function GCD(a,b)
while b c = a a = b b = c mod b wend GCD = abs(a) end function </lang>
Logo
<lang logo>to abs :n
output sqrt product :n :n
end
to gcd :m :n
output ifelse :n = 0 [ :m ] [ gcd :n modulo :m :n ]
end
to lcm :m :n
output quotient (abs product :m :n) gcd :m :n
end</lang>
Demo code:
<lang logo>print lcm 38 46</lang>
Output:
874
Lua
<lang lua>function gcd( m, n )
while n ~= 0 do local q = m m = n n = q % n end return m
end
function lcm( m, n )
return ( m ~= 0 and n ~= 0 ) and m * n / gcd( m, n ) or 0
end
print( lcm(12,18) )</lang>
Maple
The least common multiple of two integers is computed by the built-in procedure ilcm in Maple. This should not be confused with lcm, which computes the least common multiple of polynomials. <lang Maple>> ilcm( 12, 18 );
36
</lang>
Mathematica
<lang Mathematica>LCM[18,12] -> 36</lang>
MATLAB / Octave
<lang Matlab> lcm(a,b) </lang>
Maxima
<lang maxima>lcm(a, b); /* a and b may be integers or polynomials */
/* In Maxima the gcd of two integers is always positive, and a * b = gcd(a, b) * lcm(a, b), so the lcm may be negative. To get a positive lcm, simply do */
abs(lcm(a, b))</lang>
МК-61/52
<lang>ИПA ИПB * |x| ПC ИПA ИПB / [x] П9 ИПA ИПB ПA ИП9 * - ПB x=0 05 ИПC ИПA / С/П</lang>
ML
mLite
<lang ocaml>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
</lang>
NetRexx
<lang 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
</lang>
- 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
<lang nim>proc gcd(u, v): auto =
var t = 0 u = u v = v while v != 0: t = u u = v v = t %% v abs(u)
proc lcm(a, b): auto = abs(a * b) div gcd(a, b)
echo lcm(12, 18) echo lcm(-6, 14)</lang>
Objeck
<lang objeck> class LCM {
function : Main(args : String[]) ~ Nil { IO.Console->Print("lcm(35, 21) = ")->PrintLine(lcm(21,35)); } function : lcm(m : Int, n : Int) ~ Int { return m / gcd(m, n) * n; } function : gcd(m : Int, n : Int) ~ Int { tmp : Int; while(m <> 0) { tmp := m; m := n % m; n := tmp; }; return n; }
} </lang>
OCaml
<lang ocaml>let rec gcd u v =
if v <> 0 then (gcd v (u mod v)) else (abs u)
let lcm m n =
match m, n with | 0, _ | _, 0 -> 0 | m, n -> abs (m * n) / (gcd m n)
let () =
Printf.printf "lcm(35, 21) = %d\n" (lcm 21 35)</lang>
Oforth
lcm is already defined into Integer class : <lang Oforth>12 18 lcm</lang>
ooRexx
<lang ooRexx> say lcm(18, 12)
-- calculate the greatest common denominator of a numerator/denominator pair
- routine gcd private
use arg x, y
loop while y \= 0 -- check if they divide evenly temp = x // y x = y y = temp end return x
-- calculate the least common multiple of a numerator/denominator pair
- routine lcm private
use arg x, y return x / gcd(x, y) * y
</lang>
Order
<lang c>#include <order/interpreter.h>
- define ORDER_PP_DEF_8gcd ORDER_PP_FN( \
8fn(8U, 8V, \
8if(8isnt_0(8V), 8gcd(8V, 8remainder(8U, 8V)), 8U)))
- define ORDER_PP_DEF_8lcm ORDER_PP_FN( \
8fn(8X, 8Y, \
8if(8or(8is_0(8X), 8is_0(8Y)), \ 0, \ 8quotient(8times(8X, 8Y), 8gcd(8X, 8Y)))))
// No support for negative numbers
ORDER_PP( 8to_lit(8lcm(12, 18)) ) // 36</lang>
PARI/GP
Built-in function: <lang parigp>lcm</lang>
Pascal
<lang pascal>Program LeastCommonMultiple(output);
function lcm(a, b: longint): longint;
begin lcm := a; while (lcm mod b) <> 0 do inc(lcm, a); end;
begin
writeln('The least common multiple of 12 and 18 is: ', lcm(12, 18));
end.</lang> Output:
The least common multiple of 12 and 18 is: 36
Perl
Using GCD: <lang Perl>sub gcd { my ($a, $b) = @_; while ($a) { ($a, $b) = ($b % $a, $a) } $b }
sub lcm { my ($a, $b) = @_; ($a && $b) and $a / gcd($a, $b) * $b or 0 }
print lcm(1001, 221);</lang> Or by repeatedly increasing the smaller of the two until LCM is reached:<lang perl>sub lcm { use integer; my ($x, $y) = @_; my ($a, $b) = @_; while ($a != $b) { ($a, $b, $x, $y) = ($b, $a, $y, $x) if $a > $b; $a = $b / $x * $x; $a += $x if $a < $b; } $a }
print lcm(1001, 221);</lang>
Perl 6
This function is provided as an infix so that it can be used productively with various metaoperators. <lang Perl 6>say 3 lcm 4; # infix say [lcm] 1..20; # reduction say ~(1..10 Xlcm 1..10) # cross</lang>
- Output:
12 232792560 1 2 3 4 5 6 7 8 9 10 2 2 6 4 10 6 14 8 18 10 3 6 3 12 15 6 21 24 9 30 4 4 12 4 20 12 28 8 36 20 5 10 15 20 5 30 35 40 45 10 6 6 6 12 30 6 42 24 18 30 7 14 21 28 35 42 7 56 63 70 8 8 24 8 40 24 56 8 72 40 9 18 9 36 45 18 63 72 9 90 10 10 30 20 10 30 70 40 90 10
Phix
<lang Phix>function lcm(integer m, integer n)
return m / gcd(m, n) * n
end function</lang>
PHP
<lang php>echo lcm(12, 18) == 36;
function lcm($m, $n) {
if ($m == 0 || $n == 0) return 0; $r = ($m * $n) / gcd($m, $n); return abs($r);
}
function gcd($a, $b) {
while ($b != 0) { $t = $b; $b = $a % $b; $a = $t; } return $a;
}</lang>
PicoLisp
Using 'gcd' from Greatest common divisor#PicoLisp: <lang PicoLisp>(de lcm (A B)
(abs (*/ A B (gcd A B))) )</lang>
PL/I
<lang PL/I> /* Calculate the Least Common Multiple of two integers. */
LCM: procedure options (main); /* 16 October 2013 */
declare (m, n) fixed binary (31);
get (m, n); put edit ('The LCM of ', m, ' and ', n, ' is', LCM(m, n)) (a, x(1));
LCM: procedure (m, n) returns (fixed binary (31));
declare (m, n) fixed binary (31) nonassignable;
if m = 0 | n = 0 then return (0); return (abs(m*n) / GCD(m, n));
end LCM;
GCD: procedure (a, b) returns (fixed binary (31)) recursive;
declare (a, b) fixed binary (31);
if b = 0 then return (a);
return (GCD (b, mod(a, b)) );
end GCD; end LCM; </lang>
The LCM of 14 and 35 is 70
PowerShell
version 1
<lang PowerShell> 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 </lang>
version 2
version2 is faster than version1
<lang PowerShell> 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 </lang>
Output:
36
Prolog
SWI-Prolog knows gcd. <lang Prolog>lcm(X, Y, Z) :- Z is abs(X * Y) / gcd(X,Y).</lang>
Example:
?- lcm(18,12, Z). Z = 36.
PureBasic
<lang PureBasic>Procedure GCDiv(a, b); Euclidean algorithm
Protected r While b r = b b = a%b a = r Wend ProcedureReturn a
EndProcedure
Procedure LCM(m,n)
Protected t If m And n t=m*n/GCDiv(m,n) EndIf ProcedureReturn t*Sign(t)
EndProcedure</lang>
Python
gcd
Using the fractions libraries gcd function: <lang python>>>> import fractions >>> def lcm(a,b): return abs(a * b) / fractions.gcd(a,b) if a and b else 0
>>> lcm(12, 18) 36 >>> lcm(-6, 14) 42 >>> assert lcm(0, 2) == lcm(2, 0) == 0 >>> </lang>
Prime decomposition
This imports Prime decomposition#Python <lang python>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</lang>
Iteration over multiples
<lang python>>>> def lcm(*values): values = set([abs(int(v)) for v in values]) if values and 0 not in values: n = n0 = max(values) values.remove(n) while any( n % m for m in values ): n += n0 return n return 0
>>> lcm(-6, 14) 42 >>> lcm(2, 0) 0 >>> lcm(12, 18) 36 >>> lcm(12, 18, 22) 396 >>> </lang>
Repeated modulo
<lang python>>>> def lcm(p,q): p, q = abs(p), abs(q) m = p * q if not m: return 0 while True: p %= q if not p: return m // q q %= p if not q: return m // p
>>> lcm(-6, 14)
42
>>> lcm(12, 18)
36
>>> lcm(2, 0)
0
>>> </lang>
Qi
<lang qi> (define gcd
A 0 -> A A B -> (gcd B (MOD A B)))
(define lcm A B -> (/ (* A B) (gcd A B))) </lang>
R
<lang R> "%gcd%" <- function(u, v) {ifelse(u %% v != 0, v %gcd% (u%%v), v)}
"%lcm%" <- function(u, v) { abs(u*v)/(u %gcd% v)}
print (50 %lcm% 75) </lang>
Racket
Racket already has defined both lcm and gcd funtions: <lang Racket>#lang racket (lcm 3 4 5 6) ;returns 60 (lcm 8 108) ;returns 216 (gcd 8 108) ;returns 4 (gcd 108 216 432) ;returns 108</lang>
Retro
This is from the math extensions library included with Retro.
<lang Retro>: gcd ( ab-n ) [ tuck mod dup ] while drop ;
- lcm ( ab-n ) 2over gcd [ * ] dip / ;</lang>
REXX
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). <lang rexx>/*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 $ ! $; !=abs(!) /*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.*/</lang>
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,---) <lang rexx>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>
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.
The performance improvement is more significant with ooRexx than with Regina.
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>
- Output:
Output of rexx lcmt and regina lcmt cut and pasted together:
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
Ring
<lang> 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
</lang>
Ruby
Ruby has an Integer#lcm method, which finds the least common multiple of two integers.
<lang ruby>irb(main):001:0> 12.lcm 18 => 36</lang>
I can also write my own lcm method. This one takes any number of arguments.
<lang ruby>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</lang>
- Output:
396 210
Run BASIC
<lang runbasic>print lcm(22,44)
function lcm(m,n)
while n t = m m = n n = t mod n wend
lcm = m end function</lang>
Rust
This implementation uses a recursive implementation of Stein's algorithm to calculate the gcd. <lang rust>use std::cmp::{min, max}; fn gcd_stein(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_stein(a,b)
}</lang>
Scala
<lang scala>def gcd(a: Int, b: Int):Int=if (b==0) a.abs else gcd(b, a%b) def lcm(a: Int, b: Int)=(a*b).abs/gcd(a,b)</lang> <lang scala>lcm(12, 18) // 36 lcm( 2, 0) // 0 lcm(-6, 14) // 42</lang>
Scheme
<lang scheme>> (lcm 108 8) 216</lang>
Seed7
<lang seed7>$ include "seed7_05.s7i";
const func integer: gcd (in var integer: a, in var integer: b) is func
result var integer: gcd is 0; local var integer: help is 0; begin while a <> 0 do help := b rem a; b := a; a := help; end while; gcd := b; end func;
const func integer: lcm (in integer: a, in integer: b) is
return a div gcd(a, b) * b;
const proc: main is func
begin writeln("lcm(35, 21) = " <& lcm(21, 35)); end func;</lang>
Original source: [1]
Sidef
Built-in: <lang ruby>say Math.lcm(1001, 221)</lang>
Using GCD: <lang ruby>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)</lang>
- Output:
17017
Smalltalk
Smalltalk has a built-in lcm
method on SmallInteger
:
<lang smalltalk>12 lcm: 18</lang>
Sparkling
<lang 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); }</lang>
Swift
Using the Swift GCD function. <lang Swift>func lcm(a:Int, b:Int) -> Int {
return abs(a * b) / gcd_rec(a, b)
}</lang>
Tcl
<lang tcl>proc lcm {p q} {
set m [expr {$p * $q}] if {!$m} {return 0} while 1 {
set p [expr {$p % $q}] if {!$p} {return [expr {$m / $q}]} set q [expr {$q % $p}] if {!$q} {return [expr {$m / $p}]}
}
}</lang> Demonstration <lang tcl>puts [lcm 12 18]</lang> Output:
36
TI-83 BASIC
<lang ti83b>lcm(12,18
36</lang>
TSE SAL
<lang TSESAL>// library: math: get: least: common: multiple <description></description> <version control></version control> <version>1.0.0.0.2</version> <version control></version control> (filenamemacro=getmacmu.s) [<Program>] [<Research>] [kn, ri, su, 20-01-2013 14:36:11] INTEGER PROC FNMathGetLeastCommonMultipleI( INTEGER x1I, INTEGER x2I )
// RETURN( x1I * x2I / FNMathGetGreatestCommonDivisorI( x1I, x2I ) ) //
END
// library: math: get: greatest: common: divisor <description>greatest common divisor whole numbers. Euclid's algorithm. Recursive version</description> <version control></version control> <version>1.0.0.0.3</version> <version control></version control> (filenamemacro=getmacdi.s) [<Program>] [<Research>] [kn, ri, su, 20-01-2013 14:22:41] INTEGER PROC FNMathGetGreatestCommonDivisorI( INTEGER x1I, INTEGER x2I )
// IF ( x2I == 0 ) // RETURN( x1I ) // ENDIF // RETURN( FNMathGetGreatestCommonDivisorI( x2I, x1I MOD x2I ) ) //
END
PROC Main()
// STRING s1[255] = "10" STRING s2[255] = "20" REPEAT IF ( NOT ( Ask( "math: get: least: common: multiple: x1I = ", s1, _EDIT_HISTORY_ ) ) AND ( Length( s1 ) > 0 ) ) RETURN() ENDIF IF ( NOT ( Ask( "math: get: least: common: multiple: x2I = ", s2, _EDIT_HISTORY_ ) ) AND ( Length( s2 ) > 0 ) ) RETURN() ENDIF Warn( FNMathGetLeastCommonMultipleI( Val( s1 ), Val( s2 ) ) ) // gives e.g. 10 UNTIL FALSE
END</lang>
TXR
<lang bash>$ txr -p '(lcm (expt 2 123) (expt 6 49) 17)' 43259338018880832376582582128138484281161556655442781051813888</lang>
uBasic/4tH
<lang>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</lang>
- Output:
LCM of 12 : 18 = 36 0 OK, 0:330
UNIX Shell
<lang bash>gcd() { # Calculate $1 % $2 until $2 becomes zero. until test 0 -eq "$2"; do # Parallel assignment: set -- 1 2 set -- "$2" "`expr "$1" % "$2"`" done
# Echo absolute value of $1. test 0 -gt "$1" && set -- "`expr 0 - "$1"`" echo "$1" }
lcm() { set -- "$1" "$2" "`gcd "$1" "$2"`" set -- "`expr "$1" \* "$2" / "$3"`" test 0 -gt "$1" && set -- "`expr 0 - "$1"`" echo "$1" }
lcm 30 -42
- => 210</lang>
C Shell
<lang csh>alias gcd eval \set gcd_args=( \!*:q ) \\ @ gcd_u=$gcd_args[2] \\ @ gcd_v=$gcd_args[3] \\ while ( $gcd_v != 0 ) \\ @ gcd_t = $gcd_u % $gcd_v \\ @ gcd_u = $gcd_v \\ @ gcd_v = $gcd_t \\ end \\ if ( $gcd_u < 0 ) @ gcd_u = - $gcd_u \\ @ $gcd_args[1]=$gcd_u \\ '\'
alias lcm eval \set lcm_args=( \!*:q ) \\ @ lcm_m = $lcm_args[2] \\ @ lcm_n = $lcm_args[3] \\ gcd lcm_d $lcm_m $lcm_n \\ @ lcm_r = ( $lcm_m * $lcm_n ) / $lcm_d \\ if ( $lcm_r < 0 ) @ lcm_r = - $lcm_r \\ @ $lcm_args[1] = $lcm_r \\ '\'
lcm result 30 -42 echo $result
- => 210</lang>
Ursa
<lang ursa>import "math" out (lcm 12 18) endl console</lang>
- Output:
36
Vala
<lang vala> int lcm(int a, int b){
/*Return least common multiple of two ints*/ // check for 0's if (a == 0 || b == 0)
return 0;
// Math.abs(x) only works for doubles, Math.absf(x) for floats if (a < 0) a *= -1; if (b < 0)
b *= -1;
int x = 1; while (true){ if (a * x % b == 0) return a*x; x++; }
}
void main(){
int a = 12; int b = 18;
stdout.printf("lcm(%d, %d) = %d\n", a, b, lcm(a, b));
} </lang>
VBScript
<lang vb>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</lang>
- 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 <lang wortel>@lcm a b</lang> Number expression <lang wortel>!#~km a b</lang> Function (using gcd) <lang wortel>&[a b] *b /a @gcd a b</lang>
XPL0
<lang XPL0>include c:\cxpl\codes;
func GCD(M,N); \Return the greatest common divisor of M and N int M, N; int T; [while N do \Euclid's method
[T:= M; M:= N; N:= rem(T/N)];
return M; ];
func LCM(M,N); \Return least common multiple int M, N; return abs(M*N) / GCD(M,N);
\Display the LCM of two integers entered on command line IntOut(0, LCM(IntIn(8), IntIn(8)))</lang>
zkl
<lang zkl>fcn lcm(m,n){ (m*n).abs()/m.gcd(n) } // gcd is a number method</lang>
- Output:
zkl: lcm(12,18) 36 zkl: lcm(-6,14) 42 zkl: lcm(35,0) 0
- Programming Tasks
- Solutions by Programming Task
- 8th
- Ada
- ALGOL 68
- ALGOL W
- APL
- AppleScript
- Arendelle
- Assembly
- X86 Assembly
- AutoHotkey
- AutoIt
- AWK
- BASIC
- Applesoft BASIC
- BBC BASIC
- Batch File
- Bc
- Bracmat
- Brat
- C
- C++
- Boost
- C sharp
- Clojure
- COBOL
- Common Lisp
- D
- DWScript
- Dart
- EchoLisp
- Elixir
- Erlang
- ERRE
- Euphoria
- Excel
- Ezhil
- F Sharp
- Factor
- Forth
- Fortran
- FreeBASIC
- Frink
- FunL
- GAP
- Go
- Groovy
- Haskell
- Icon
- Unicon
- Icon Programming Library
- J
- Java
- JavaScript
- Jq
- Julia
- K
- Kotlin
- LabVIEW
- Lasso
- Liberty BASIC
- Logo
- Lua
- Maple
- Mathematica
- MATLAB
- Octave
- Maxima
- МК-61/52
- ML
- MLite
- NetRexx
- Nim
- Objeck
- OCaml
- Oforth
- OoRexx
- Order
- PARI/GP
- Pascal
- Perl
- Perl 6
- Phix
- PHP
- PicoLisp
- PL/I
- PowerShell
- Prolog
- PureBasic
- Python
- Qi
- R
- Racket
- Retro
- REXX
- Ring
- Ruby
- Run BASIC
- Rust
- Scala
- Scheme
- Seed7
- Sidef
- Smalltalk
- Sparkling
- Swift
- Tcl
- TI-83 BASIC
- TSE SAL
- TXR
- UBasic/4tH
- UNIX Shell
- C Shell
- Ursa
- Vala
- VBScript
- Wortel
- XPL0
- Zkl