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.
The least common multiple of 12 and 18 is 36, because:
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 forgreatest common divisor, then this formula calculates lcm.
One can also find lcm by merging theprime decompositions of both m and n.
F gcd(=a, =b) L b != 0 (a, b) = (b, a % b) R aF lcm(m, n) R m I/ gcd(m, n) * nprint(lcm(12, 18))
36
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=aLOOPW 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 whileELOOPW 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 callerA DC F'1764' aB DC F'3920' bPG DC CL80'lcm(00000,00000)=0000000000' buffer XDEC DS CL12 temp for edit YREGS END LCM
lcm( 1764, 3920)= 35280
:gcd\ a b -- gcddup0n:=ifdrop;;thentuck\ b a bn:mod\ b a-mod-brecurse;:lcm\ m n2dup\ m n m nn:*\ m n m*nn:abs\ m n abs(m*n)-rot\ abs(m*n) m ngcd\ abs(m*n) gcd(m.n)n:/mod\ abs / gcdnip\ abs div gcd;:demo\ n m --2dup"LCMof".."and".."=".lcm.;1218democr-614democr350democrbye
LCM of 18 and 12 = 36LCM of 14 and -6 = 42LCM of 0 and 35 = 0
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 ODRETURN(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)RETURNPROC Main() Test(4,6) Test(120,77) Test(24,8) Test(1,56) Test(12,0)RETURNScreenshot from Atari 8-bit computer
LCM of 4 and 6 is 12LCM of 120 and 77 is 9240LCM of 24 and 8 is 24LCM of 1 and 56 is 56LCM of 12 and 0 is 0
lcm_test.adb:
withAda.Text_IO;useAda.Text_IO;procedureLcm_TestisfunctionGcd(A,B:Integer)returnIntegerisM:Integer:=A;N:Integer:=B;T:Integer;beginwhileN/=0loopT:=M;M:=N;N:=TmodN;endloop;returnM;endGcd;functionLcm(A,B:Integer)returnIntegerisbeginifA=0orB=0thenreturn0;endif;returnabs(A)*(abs(B)/Gcd(A,B));endLcm;beginPut_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)));endLcm_Test;
Output:
LCM of 12, 18 is 36LCM of -6, 14 is 42LCM of 35, 0 is 0
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
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.
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 provides this function.
12^1836
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←{(|⍺×⍵)÷⍺∨⍵}12LCM1836
------------------ LEAST COMMON MULTIPLE ------------------- lcm :: Integral a => a -> a -> aonlcm(x,y)if0=xor0=ythen0elseabs(xdiv(gcd(x,y))*y)endifendlcm--------------------------- TEST -------------------------onrunlcm(12,18)--> 36endrun-------------------- GENERIC FUNCTIONS --------------------- abs :: Num a => a -> aonabs(x)if0>xthen-xelsexendifendabs-- gcd :: Integral a => a -> a -> aongcd(x,y)scripton|λ|(a,b)if0=bthenaelse|λ|(b,amodb)endifend|λ|endscriptresult's|λ|(abs(x),abs(y))endgcd
36For GCD function check outhere
< a , b >( return , abs ( @a * @b ) / !gcd( @a , @b ))
lcm:function[x,y][x*y/gcd@[xy]]printlcm1218
36
; 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]globalmainexternprintf; c function: prints formatted outputexternstrtol; c function: converts strings to longssection.textmain:pushrbp; set up stack frame; rdi contains argc; if less than 3, exitcmprdi,3jlincorrect_usage; push first argument as numberpushrsimovrdi,[rsi+8]movrsi,0movrdx,10; base 10callstrtolpoprsipushrax; push second argument as numberpushrsimovrdi,[rsi+16]movrsi,0movrdx,10; base 10callstrtolpoprsipushrax; pop arguments and call get_gcdpoprdipoprsicallget_gcd; print valuemovrdi,print_numbermovrsi,raxcallprintf; exitmovrax,0; 0--exit successpoprbpretincorrect_usage:movrdi,bad_use_string; rsi already contains argvmovrsi,[rsi]callprintfmovrax,0; 0--exit successpoprbpretbad_use_string:db"Usage:%s[number1][number2]",10,0print_number:db"%d",10,0get_gcd:pushrbp; set up stack framemovrax,0jmplooploop:; keep adding the first argument; to itself until a multiple; is found. then, returnaddrax,rdipushraxmovrdx,0divrsicmprdx,0popraxjegcd_foundjmploopgcd_found:poprbpret
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_unsignedoverload lcm with g0uint_lcmoverload 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 endimplement {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. *)(* *)implementmain0 () = 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) endLCM(Number1,Number2){If(Number1=0||Number2=0)ReturnVar:=Number1*Number2While,Number2Num:=Number2,Number2:=Mod(Number1,Number2),Number1:=NumReturn,Var//Number1}Num1=12Num2=18MsgBox%LCM(Num1,Num2)
Func_LCM($a,$b)Local$c,$f,$m=$a,$n=$b$c=1While$c<>0$f=Int($a/$b)$c=$a-$b*$fIf$c<>0Then$a=$b$b=$cEndIfWEndReturn$m*$n/$bEndFunc;==>_LCM
Example
ConsoleWrite(_LCM(12,18)&@LF)ConsoleWrite(_LCM(-5,12)&@LF)ConsoleWrite(_LCM(13,0)&@LF)
36600
--BugFix (talk) 14:32, 15 November 2013 (UTC)
# greatest common divisorfunctiongcd(m,n,t){# Euclid's methodwhile(n!=0){t=mm=nn=t%n}returnm}# least common multiplefunctionlcm(m,n,r){if(m==0||n==0)return0r=m*n/gcd(m,n)returnr<0?-r:r}# Read two integers from each line of input.# Print their least common multiple.{printlcm($1,$2)}
Example input and output:
$ awk -f lcd.awk12 1836-6 144235 00
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 10050 PRINT R60 END100 REM LEAST COMMON MULTIPLE M% N%110 R = 0120 IF M% = 0 OR N% = 0 THEN RETURN130 A% = M% : B% = N% : GOSUB 200"GCD140 R = ABS(M%*N%)/R150 RETURN200 REM GCD ITERATIVE EUCLID A% B%210 FOR B = B% TO 0 STEP 0220 C% = A%230 A% = B240 B = FN MOD(C%)250 NEXT B260 R = ABS(A%)270 RETURN
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%)
100 DEF LCM(A,B)=(A*B)/GCD(A,B)110 DEF GCD(A,B)120 DO WHILE B>0130 LET T=B:LET B=MOD(A,B):LET A=T140 LOOP 150 LET GCD=A160 END DEF 170 PRINT LCM(12,18)
10PRINT"First number"20INPUTA30PRINT"Second number"40INPUTB42LETQ=A44LETR=B50IFQ<0THENLETQ=-Q60IFR<0THENLETR=-R70IFQ>RTHENGOTO13080LETR=R-Q90IFQ=0THENGOTO110100GOTO50110LETU=(A*B)/R111IFU<0THENLETU=-U112PRINTU120END130LETC=Q140LETQ=R150LETR=C160GOTO70
function mcm (m, n)if m = 0 or n = 0 then return 0if m < n thent = m : m = n : n = tend ifcont = 0docont += 1until (m * cont) mod n = 0return m * contend functionprint "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)
lcm( 12, 18) = 36lcm( 15, 12) = 60lcm(-10, -14) = -70lcm( 0, 1) = 0
Reuses code from Greatest_common_divisor#Recursive_solution and correctly handles negative arguments
function gcdp(a, b)if b = 0 then return areturn gcdp(b, a mod b)end functionfunction gcd(a, b)return gcdp(abs(a), abs(b))end functionfunction lcm(a, b)return abs(a * b) / gcd(a, b)end functionprint "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)
lcm( 12, -18) = 36.0lcm( 15, 12) = 60.0lcm(-10, -14) = 70.0lcm( 0, 1) = 0.0
@echo offsetlocal enabledelayedexpansionsetnum1=12setnum2=18call:lcm%num1%%num2%exit /b:lcm <input1> <input2>if%2equ 0(set/alcm=%num1%*%num2%/%1echo LCM =!lcm!pause>nulgoto:EOF)set/ares=%1%%%2call:lcm%2%res%goto:EOF
LCM = 36
/* greatest common divisor */define g(m, n){auto t/* Euclid's method */while(n!=0){t= mm= nn= t% n}return(m)}/* least common multiple */define l(m, n){auto rif(m==0|| n==0)return(0)r= m* n/ g(m, n)if(r<0)return(-r)return(r)}
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))36
Inputs are limited to signed 16-bit integers.
&>:0`2*1-*:&>:#@!#._:0`2*1v>28*:*:**+:28*>:*:*/\:vv*-<|<:%/*:*:*82\%*:*:*82<<>28v>$/28*:*:*/*.@^82::+**:*:*<
12345-23044
345660
Lcm←×÷{𝕨(|𝕊⍟(>⟜0)⊣)𝕩}
Example:
12Lcm18
36
We utilize the fact that Bracmat simplifies fractions (using Euclid's algorithm). The functionden$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
gcd = { a, b | true? { a == 0 } { b } { gcd(b % a, a) }}lcm = { a, b | a * b / gcd(a, b)}p lcm(12, 18) # 36p lcm(14, 21) # 42: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]])
#include<stdio.h>intgcd(intm,intn){inttmp;while(m){tmp=m;m=n%m;n=tmp;}returnn;}intlcm(intm,intn){returnm/gcd(m,n)*n;}intmain(){printf("lcm(35, 21) = %d\n",lcm(21,35));return0;}
UsingSystem;classProgram{staticintgcd(intm,intn){returnn==0?Math.Abs(m):gcd(n,n%m);}staticintlcm(intm,intn){returnMath.Abs(m*n)/gcd(m,n);}staticvoidMain(){Console.WriteLine("lcm(12,18)="+lcm(12,18));}}
lcm(12,18)=36
#include<boost/math/common_factor.hpp>#include<iostream>intmain(){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;return0;}
The least common multiple of 12 and 18 is 36 ,and the greatest common divisor 6 !
#include<cstdlib>#include<iostream>#include<tuple>intgcd(inta,intb){a=abs(a);b=abs(b);while(b!=0){std::tie(a,b)=std::make_tuple(b,a%b);}returna;}intlcm(inta,intb){intc=gcd(a,b);returnc==0?0:a/c*b;}intmain(){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;return0;}
(defngcd[ab](if(zero?b)a(recurb,(modab))))(defnlcm[ab](/(*ab)(gcdab)));; to calculate the lcm for a variable number of arguments(defnlcmv[&v](reducelcmv))
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 gcdlcm = proc (m, n: int) returns (int) if m=0 cor n=0 then return(0) else return(int$abs(m*n) / gcd(m,n)) endend lcmstart_up = proc () po: stream := stream$primary_output() stream$putl(po, int$unparse(lcm(12, 18)))end start_up
36
IDENTIFICATIONDIVISION.PROGRAM-ID.show-lcm.ENVIRONMENTDIVISION.CONFIGURATIONSECTION.REPOSITORY.FUNCTIONlcm.PROCEDUREDIVISION.DISPLAY"lcm(35, 21) = "FUNCTIONlcm(35,21)GOBACK.ENDPROGRAMshow-lcm.IDENTIFICATIONDIVISION.FUNCTION-ID.lcm.ENVIRONMENTDIVISION.CONFIGURATIONSECTION.REPOSITORY.FUNCTIONgcd.DATADIVISION.LINKAGESECTION.01mPIC S9(8).01nPIC S9(8).01retPIC S9(8).PROCEDUREDIVISIONUSINGVALUEm,nRETURNINGret.COMPUTEret=FUNCTIONABS(m*n)/FUNCTIONgcd(m,n)GOBACK.ENDFUNCTIONlcm.IDENTIFICATIONDIVISION.FUNCTION-ID.gcd.DATADIVISION.LOCAL-STORAGESECTION.01tempPIC S9(8).01xPIC S9(8).01yPIC S9(8).LINKAGESECTION.01mPIC S9(8).01nPIC S9(8).01retPIC S9(8).PROCEDUREDIVISIONUSINGVALUEm,nRETURNINGret.MOVEmtoxMOVEntoyPERFORMUNTILy=0MOVExTOtempMOVEyTOxMOVEFUNCTIONMOD(temp,y)TOYEND-PERFORMMOVEFUNCTIONABS(x)TOretGOBACK.ENDFUNCTIONgcd.
Common Lisp provides thelcm function. It can accept two or more (or less) parameters.
CL-USER>(lcm1218)36CL-USER>(lcm121822)396
Here is one way to reimplement it.
CL-USER>(defunmy-lcm(&restargs)(reduce(lambda(mn)(cond((or(=m0)(=n0))0)(t(abs(/(*mn)(gcdmn))))))args:initial-value1))MY-LCMCL-USER>(my-lcm1218)36CL-USER>(my-lcm121822)396
In this code, thelambda finds the least common multiple of two integers, and thereduce transforms it to accept any number of parameters. Thereduce operation exploits howlcm is associative,(lcm a b c) == (lcm (lcm a b) c); and how 1 is an identity,(lcm 1 a) == a.
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();
36
importstd.stdio,std.bigint,std.math;Tgcd(T)(Ta,Tb)purenothrow{while(b){immutablet=b;b=a%b;a=t;}returna;}Tlcm(T)(Tm,Tn)purenothrow{if(m==0)returnm;if(n==0)returnn;returnabs((m*n)/gcd(m,n));}voidmain(){lcm(12,18).writeln;lcm("2562047788015215500854906332309589561".BigInt,"6795454494268282920431565661684282819".BigInt).writeln;}
3615669251240038298262232125175172002594731206081193527869
main(){intx=8;inty=12;intz=gcd(x,y);varlcm=(x*y)/z;print('$lcm');}intgcd(inta,intb){if(b==0)returna;if(b!=0)returngcd(b,a%b);}
SeePascal.
PrintLn(Lcm(12,18));
Output:
36
proc gcd(word m, n) word: word t; while n /= 0 do t := m; m := n; n := t % n od; mcorpproc lcm(word m, n) word: if m=0 or n=0 then 0 else m*n / gcd(m,n) ficorpproc main() void: writeln(lcm(12, 18))corp
36
DuckDB has a scalar function, lcm(), which is an alias for least_common_multiple().In the following typescript, "D " is the DuckDB prompt. Notice thatgcd() has several signatures. In fact, there are currently two: onefor BIGINT and the other for HUGEINT.
D select lcm(12345, 9876) as lcm;┌───────┐│ lcm ││ int64 │├───────┤│ 49380 │└───────┘D select lcm(0,1), lcm(1,0), lcm(0,0);┌───────────┬───────────┬───────────┐│ lcm(0, 1) │ lcm(1, 0) │ lcm(0, 0) ││ int64 │ int64 │ int64 │├───────────┼───────────┼───────────┤│ 0 │ 0 │ 0 │└───────────┴───────────┴───────────┘D select lcm(123456789123456789123456789123456789, 23);┌───────────────────────────────────────────────┐│ lcm(123456789123456789123456789123456789, 23) ││ int128 │├───────────────────────────────────────────────┤│ 2839506149839506149839506149839506147 │└───────────────────────────────────────────────┘
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
36
(lcm a b) is already here as a two arguments function. Use foldl to find the lcm of a list of numbers.
(lcm09)→0(lcm444888)→888(lcm888999)→7992(define(lcm*list)(foldllcm(firstlist)list))→lcm*(lcm*'(444888999))→7992
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))}lcm(12,18)=36
defmoduleRCdodefgcd(a,0),do:abs(a)defgcd(a,b),do:gcd(b,rem(a,b))deflcm(a,b),do:div(abs(a*b),gcd(a,b))endIO.putsRC.lcm(-12,15)
60
% Implemented by Arjun Sunel-module(lcm).-export([main/0]).main()->lcm(-3,4).gcd(A,0)->A;gcd(A,B)->gcd(B,AremB).lcm(A,B)->abs(A*Bdivgcd(A,B)).
12
PROGRAM LCMPROCEDURE GCD(A,B->GCD) LOCAL C WHILE B DO C=A A=B B=C MOD B END WHILE GCD=ABS(A)END PROCEDUREPROCEDURE 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 IFEND PROCEDUREBEGIN 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 PROGRAMLCM of 18 and 12 = 36LCM of 14 and -6 = 42LCM of 0 and 35 = 0
Note % is integer division in Euler, not the mod operator.
beginnew gcd;new lcm; gcd <- `formal a;formal b;if b = 0then aelse gcd( b, amodabs b ) ' ; lcm <- `formal a;formal b;abs [ a * b ] % gcd( a, b ) ' ;out lcm( 15, 20 )end $
function gcd(integer m, integer n) integer tmp while m do tmp = m m = remainder(n,m) n = tmp end while return nend functionfunction lcm(integer m, integer n) return m / gcd(m, n) * nend function
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 :
1235231367159423605940
## இந்த நிரல் இரு எண்களுக்கு இடையிலான மீச்சிறு பொது மடங்கு (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) = ", மீபொம(அ, ஆ)letrecgcdxy=ify=0thenabsxelsegcdy(x%y)letlcmxy=x*y/(gcdxy)
The vocabularymath.functions already provideslcm.
USING:math.functionsprettyprint;26 28lcm.
This program outputs364.
One can also reimplementlcm.
USING:kernelmathprettyprint;IN:script:gcd(ab--c)[abs][[nip][mod]2bigcd]if-zero;:lcm(ab--c)[*abs][gcd]2bi/;26 28lcm.
Func Lecm(a,b)=|a|*|b|/GCD(a,b).
:gcd( a b -- n )begindupwhiletuckmodrepeatdrop;:lcm( a b -- n )over0=over0=orif2drop0exitthen2dupgcdabs*/;
This solution is written as a combination of 2 functions, but a subroutine implementation would work great as well.
integerfunctionlcm(a,b)integer::a,blcm=a*b/gcd(a,b)end functionlcmintegerfunctiongcd(a,b)integer::a,b,tdo while(b/=0)t=bb=mod(a,b)a=tend dogcd=abs(a)end functiongcd
' FB 1.05.0 Win64Functionlcm(mAsInteger,nAsInteger)AsIntegerIfm=0OrElsen=0ThenReturn0Ifm<nThenSwapm,n'' to minimize iterations neededVarcount=0Docount+=1LoopUntil(m*count)Modn=0Returnm*countEndFunctionPrint"lcm(12, 18) =";lcm(12,18)Print"lcm(15, 12) =";lcm(15,12)Print"lcm(10, 14) =";lcm(10,14)PrintPrint"Press any key to quit"Sleep
lcm(12, 18) = 36lcm(15, 12) = 60lcm(10, 14) = 70
Reuses code fromGreatest_common_divisor#Recursive_solution and correctly handles negative arguments
functiongcdp(aasuinteger,basuinteger)asuintegerifb=0thenreturnareturngcdp(b,amodb)endfunctionfunctiongcd(aasinteger,basinteger)asuintegerreturngcdp(abs(a),abs(b))endfunctionfunctionlcm(aasinteger,basinteger)asuintegerreturnabs(a*b)/gcd(a,b)endfunctionprint"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)
lcm( 12, -18) = 36lcm( 15, 12) = 60lcm(-10, -14) = 70lcm( 0, 1) = 0
Frink has a built-in LCM function that handles arbitrarily-large integers.
println[lcm[2562047788015215500854906332309589561, 6795454494268282920431565661684282819]]
FunL has functionlcm in moduleintegers with the following definition:
def lcm( _, 0 ) = 0 lcm( 0, _ ) = 0 lcm( x, y ) = abs( (x\gcd(x, y)) y )
int local fn gcd_rec( a as int, b as int ) if ( b == 0 ) then return aend fn = fn gcd_rec(b, a % b)int def fn lcm( a as int, b as int ) = abs(a * b) / fn gcd_rec(a, b)print fn lcm(12,18)HandleEvents
36
# Built-inLcmInt(12,18);# 36
packagemainimport("fmt""math/big")varm,n,zbig.Intfuncinit(){m.SetString("2562047788015215500854906332309589561",10)n.SetString("6795454494268282920431565661684282819",10)}funcmain(){fmt.Println(z.Mul(z.Div(&m,z.GCD(nil,nil,&m,&n)),&n))}
15669251240038298262232125175172002594731206081193527869
{{.@\%.}do;}:gcd;{.@.@gcd@@*\/}:lcm;2706 410 lcm print13530
defgcdgcd={m,n->m=m.abs();n=n.abs();n==0?m:m%n==0?n:gcd(n,m%n)}deflcd={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"assertlcd(t.m,t.n)==t.l}
LCD of 12, 18 is 36LCD of -6, 14 is 42LCD of 35, 0 is 0
10PRINT"LCM(35, 21) = ";20LETMLCM=3530LETNLCM=2140GOSUB200:' Calculate LCM50PRINTLCM60END195' Calculate LCM200LETMGCD=MLCM210LETNGCD=NLCM220GOSUB400:' Calculate GCD230LETLCM=MLCM/GCD*NLCM240RETURN395' Calculate GCD400WHILEMGCD<>0410LETTMP=MGCD420LETMGCD=NGCDMODMGCD430LETNGCD=TMP440WEND450LETGCD=NGCD460RETURN
That is already available as the functionlcm in the Prelude. Here's the implementation:
lcm::(Integrala)=>a->a->alcm_0=0lcm0_=0lcmxy=abs((x`quot`(gcdxy))*y)
The lcm routine from the Icon Programming Library uses gcd. The routine is
linknumbersproceduremain()write("lcm of 18, 36 = ",lcm(18,36))write("lcm of 0, 9 = ",lcm(0,9))end
numbers provides lcm and gcd and looks like this:
procedurelcm(i,j)#: least common multipleif(i=0)|(j=0)thenreturn0returnabs(i*j)/gcd(i,j)end
J provides the dyadic verb*. which returns the least common multiple of its left and right arguments.
12*.183612*.182236132*./1218223960101*.0011NB. for truth valued arguments (0 and 1) it is equivalent to "and"0001*./~010001
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)).
importjava.util.Scanner;publicclassLCM{publicstaticvoidmain(String[]args){ScanneraScanner=newScanner(System.in);//prompts user for values to find the LCM for, then saves them to m and nSystem.out.print("Enter the value of m:");intm=aScanner.nextInt();System.out.print("Enter the value of n:");intn=aScanner.nextInt();intlcm=(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){intmm=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);}}
Computing the least common multiple of an integer array, using the associative law:
functionLCM(A)// A is an integer array (e.g. [-50,25,-45,-18,90,447]){varn=A.length,a=Math.abs(A[0]);for(vari=1;i<n;i++){varb=Math.abs(A[i]),c=a;while(a&&b){a>b?a%=b:b%=a;}a=Math.abs(c*A[i])/(a+b);}returna;}/* For example: LCM([-50,25,-45,-18,90,447]) -> 67050*/
(()=>{'use strict';// gcd :: Integral a => a -> a -> aletgcd=(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 -> aletlcm=(x,y)=>x===0||y===0?0:Math.abs(Math.floor(x/gcd(x,y))*y);// TESTreturnlcm(12,18);})();
36
Direct method
# Define the helper function to take advantage of jq's tail-recursion optimizationdef 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;
Built-in function:
lcm(m,n)
gcd:{:[~x;y;_f[y;x!y]]}lcm:{_abs_x*y%gcd[x;y]}lcm.'(1218;-614;350)36420lcm/1+!20232792560
abs:|/-:\gcd:{$[~x;y;o[x!y;x]]}lcm:{abs[`i$x*y%gcd[x;y]]}lcm.'(1218;-614;350)36420lcm/1+!20232792560
: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 " inputfunmain(args:Array<String>){fungcd(a:Long,b:Long):Long=if(b==0L)aelsegcd(b,a%b)funlcm(a:Long,b:Long):Long=a/gcd(a,b)*bprintln(lcm(15,9))}
RequiresGCD. This image is aVI Snippet, an executable image ofLabVIEW 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.
definegcd(a,b)=>{while(#b!=0)=>{local(t=#b)#b=#a%#b#a=#t}return#a}definelcm(m,n)=>{#m==0||#n==0?return0local(r=(#m*#n)/decimal(gcd(#m,#n)))returninteger(#r)->abs}lcm(-6,14)lcm(2,0)lcm(12,18)lcm(12,22)lcm(7,31)
42036132217
print "Least Common Multiple of 12 and 18 is "; LCM(12, 18)endfunction LCM(m, n) LCM = abs(m * n) / GCD(m, n)end functionfunction GCD(a, b) while b c = a a = b b = c mod b wend GCD = abs(a)end function
to abs :n output sqrt product :n :nendto gcd :m :n output ifelse :n = 0 [ :m ] [ gcd :n modulo :m :n ]endto lcm :m :n output quotient (abs product :m :n) gcd :m :nend
Demo code:
print lcm 38 46
Output:
874
functiongcd(m,n)whilen~=0dolocalq=mm=nn=q%nendreturnmendfunctionlcm(m,n)return(m~=0andn~=0)andm*n/gcd(m,n)or0endprint(lcm(12,18))
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`'dnldnllcm(-6, 14) = 42lcm(2, 0) = 0lcm(12, 18) = 36lcm(12, 22) = 132lcm(7, 31) = 21742 = 420 = 036 = 36132 = 132217 = 217
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
LCM[18,12]->36
lcm(a,b)
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))
Textwindow.Write("LCM(35, 21) = ")mlcm = 35nlcm = 21CalculateLCM()TextWindow.WriteLine(lcm)Sub CalculateLCM mgcd = mlcm ngcd = nlcm CalculateGCD() lcm = mlcm / gcd * nlcmEndSub Sub CalculateGCD While mgcd <> 0 tmp = mgcd mgcd = Math.Remainder(ngcd, mgcd) ngcd = tmp EndWhile gcd = ngcdEndSubgcd=function(a,b)whilebtemp=bb=a%ba=tempendwhilereturnabs(a)endfunctionlcm=function(a,b)ifnotaandnotbthenreturn0returnabs(a*b)/gcd(a,b)endfunctionprintlcm(18,12)
36
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"];36
((0 <) (-1 *) when) :abs((dup 0 ==) (pop abs) (swap over mod) () linrec) :gcd(over over gcd '* dip div) :lcm
ИПAИПB*|x|ПCИПAИПB/[x]П9ИПAИПBПAИП9*-ПBx=005ИПCИПA/С/П
fungcd(a,0)=a|(0,b)=b|(a,b)where(a<b)=gcd(a,brema)|(a,b)=gcd(b,aremb)funlcm(a,b)=letvald=gcd(a,b)ina*bdivdend
MODULELeastCommonMultiple;FROMSTextIOIMPORTWriteString,WriteLn;FROMSWholeIOIMPORTWriteInt;PROCEDUREGCD(M,N:INTEGER):INTEGER;VARTmp:INTEGER;BEGINWHILEM<>0DOTmp:=M;M:=NMODM;N:=Tmp;END;RETURNN;ENDGCD;PROCEDURELCM(M,N:INTEGER):INTEGER;BEGINRETURNM/GCD(M,N)*N;ENDLCM;BEGINWriteString("LCM(35, 21) = ");WriteInt(LCM(35,21),1);WriteLn;ENDLeastCommonMultiple.
def gcd(a, b)if (a < 1) or (b < 1)throw new(InvalidNumberException, "gcd cannot be calculated on values < 1")endc = 0while b != 0c = aa = bb = c % bendreturn aenddef lcm(m, n)return (m * n) / gcd(m, n)endprintln lcm(12, 18)println lcm(6, 14)println lcm(1,2) = lcm(2,1)
3642true
/* NetRexx */optionsreplaceformatcommentsjavacrossrefsymbolsnobinarynumericdigits3000runSample(arg)return--~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~methodlcm(m_,n_)publicstaticL_=m_*n_%gcd(m_,n_)returnL_--~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~--Euclid's algorithm - iterative implementationmethodgcd(m_,n_)publicstaticloopwhilen_>0c_=m_//n_m_=n_n_=c_endreturnm_--~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~methodrunSample(arg)privatestaticparseargsamplesifsamples=''|samples='.'thensamples='-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 |'---confirmthatotherpermutationswork'12 -5 18 = 180 |'-'18 12 -5 97 = 17460 |'-'30 42 = 210 |'-'30 42 = . |'---210;noverificationrequested'18 12'--36loopwhilesamples\=''parsesamplessample'|'samplesloopwhilesample\=''parsesamplemnvals'='chksampleifchk=''thenchk='.'mv=mnvals.word(1)loopw_=2tomnvals.wordsmnvalsnv=mnvals.word(w_)mv=mv.absnv=nv.absmv=lcm(mv,nv)endw_lv=mvselectcasechkwhen'.'thenstate=''whenlvthenstate='(verified)'otherwisestate='(failed)'endmnvals=mnvals.space(1,',').changestr(',',', ')say'lcm of'mnvals.right(15.max(mnvals.length))'is'lv.right(5.max(lv.length))stateendendreturn
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
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):
procgcd(u,v:int):auto=varu=uv=vwhilev!=0:u=u%%vswapu,vabs(u)proclcm(a,b:int):auto=abs(a*b)divgcd(a,b)echolcm(12,18)echolcm(-6,14)
3642
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; }}letrecgcduv=ifv<>0then(gcdv(umodv))else(absu)letlcmmn=matchm,nwith|0,_|_,0->0|m,n->abs(m*n)/(gcdmn)let()=Printf.printf"lcm(35, 21) = %d\n"(lcm2135)
lcm is already defined into Integer class :
12 18 lcm
saylcm(18,12)--calculatethegreatestcommondenominatorofanumerator/denominatorpair::routinegcdprivateuseargx,yloopwhiley\=0--checkiftheydivideevenlytemp=x//yx=yy=tempendreturnx--calculatetheleastcommonmultipleofanumerator/denominatorpair::routinelcmprivateuseargx,yreturnx/gcd(x,y)*y
#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 numbersORDER_PP(8to_lit(8lcm(12,18)))// 36
Built-in function:
lcm
ProgramLeastCommonMultiple(output);{$IFDEF FPC}{$MODE DELPHI}{$ENDIF}functionlcm(a,b:longint):longint;beginresult:=a;while(resultmodb)<>0doinc(result,a);end;beginwriteln('The least common multiple of 12 and 18 is: ',lcm(12,18));end.
Output:
The least common multiple of 12 and 18 is: 36
functionGCD(a,b:integer):integer;beginwhileb>0do(a,b):=(b,amodb);Result:=a;end;functionLCM(a,b:integer):integer:=a=0?0:adivGCD(a,b)*b;beginPrintln(LCM(12,18));end.
36
Using GCD:
subgcd{my($x,$y)=@_;while($x){($x,$y)=($y%$x,$x)}$y}sublcm{my($x,$y)=@_;($x&&$y)and$x/gcd($x,$y)*$yor0}printlcm(1001,221);
Or by repeatedly increasing the smaller of the two until LCM is reached:
sublcm{useinteger;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+=$xif$f<$s;}$f}printlcm(1001,221);
It is a builtin function, defined in builtins\gcd.e and accepting either two numbers or a single sequence of any length.
withjavascript_semantics?lcm(12,18)?lcm({12,18})
3636
def gcd /# u v -- n #/abs int swap abs int swapdupwhileover over mod rot drop dupendwhiledropenddefdef lcm /# m n -- n #/over over gcd rot swap / *enddef12345 50 lcm print
echolcm(12,18)==36;functionlcm($m,$n){if($m==0||$n==0)return0;$r=($m*$n)/gcd($m,$n);returnabs($r);}functiongcd($a,$b){while($b!=0){$t=$b;$b=$a%$b;$a=$t;}return$a;}
Picat has a built-in functiongcd/2.
lcm(X,Y)= abs(X*Y)//gcd(X,Y).
lcm(X,Y,LCM) => LCM = abs(X*Y)//gcd(X,Y).
lcm(List) = fold(lcm,1,List).
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.(12,18) = 36(-6,14) = 42(35,0) = 0(7,10) = 70(2562047788015215500854906332309589561,6795454494268282920431565661684282819) = 156692512400382982622321251751720025947312060811935278691..20 = 2327925601..50 = 3099044504245996706400
Using 'gcd' fromGreatest common divisor#PicoLisp:
(de lcm (A B) (abs (*/ A B (gcd A B))) )
/* 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
functiongcd($a,$b){functionpgcd($n,$m){if($n-le$m){if($n-eq0){$m}else{pgcd$n($m-$n)}}else{pgcd$m$n}}$n=[Math]::Abs($a)$m=[Math]::Abs($b)(pgcd$n$m)}functionlcm($a,$b){[Math]::Abs($a*$b)/(gcd$a$b)}lcm1218
version2 is faster than version1
functiongcd($a,$b){functionpgcd($n,$m){if($n-le$m){if($n-eq0){$m}else{pgcd$n($m%$n)}}else{pgcd$m$n}}$n=[Math]::Abs($a)$m=[Math]::Abs($b)(pgcd$n$m)}functionlcm($a,$b){[Math]::Abs($a*$b)/(gcd$a$b)}lcm1218
Output:
36
SWI-Prolog knows gcd.
lcm(X,Y,Z):-Zisabs(X*Y)/gcd(X,Y).
Example:
?- lcm(18,12, Z).Z = 36.
ProcedureGCDiv(a,b);EuclideanalgorithmProtectedrWhilebr=bb=a%ba=rWendProcedureReturnaEndProcedureProcedureLCM(m,n)ProtectedtIfmAndnt=m*n/GCDiv(m,n)EndIfProcedureReturnt*Sign(t)EndProcedure
Using the fractions librariesgcd function:
>>>importfractions>>>deflcm(a,b):returnabs(a*b)/fractions.gcd(a,b)ifaandbelse0>>>lcm(12,18)36>>>lcm(-6,14)42>>>assertlcm(0,2)==lcm(2,0)==0>>>
Or, for compositional flexibility, a curriedlcm, expressed in terms of our owngcd function:
'''Least common multiple'''frominspectimportsignature# lcm :: Int -> Int -> Intdeflcm(x):'''The smallest positive integer divisible without remainder by both x and y. '''returnlambday:0if0in(x,y)elseabs(y*(x//gcd_(x)(y)))# gcd_ :: Int -> Int -> Intdefgcd_(x):'''The greatest common divisor in terms of the divisibility preordering. '''defgo(a,b):returngo(b,a%b)if0!=belseareturnlambday:go(abs(x),abs(y))# TEST ----------------------------------------------------# main :: IO ()defmain():'''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]defenumFromTo(m):'''Integer enumeration from m to n.'''returnlambdan:list(range(m,1+n))# uncurry :: (a -> b -> c) -> ((a, b) -> c)defuncurry(f):'''A function over a tuple, derived from a vanilla or curried function. '''if1<len(signature(f).parameters):returnlambdaxy:f(*xy)else:returnlambdaxy:f(xy[0])(xy[1])# unlines :: [String] -> Stringdefunlines(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] -> StringdeffTable(s):'''Heading -> x display function -> fx display function -> f -> xs -> tabular string. '''defgo(xShow,fxShow,f,xs):ys=[xShow(x)forxinxs]w=max(map(len,ys))returns+'\n'+'\n'.join(map(lambdax,y:y.rjust(w,' ')+' -> '+fxShow(f(x)),xs,ys))returnlambdaxShow:lambdafxShow:lambdaf:lambdaxs:go(xShow,fxShow,f,xs)# MAIN ---if__name__=='__main__':main()
Least common multiples of 60 and [12..20]:12 -> 6013 -> 78014 -> 42015 -> 6016 -> 24017 -> 102018 -> 18019 -> 114020 -> 60Least common multiples of [(0, 2), (2, 0), (-6, 14), (12, 18)]: (0, 2) -> 0 (2, 0) -> 0(-6, 14) -> 42(12, 18) -> 36
This importsPrime decomposition#Python
fromprime_decompositionimportdecomposetry:reduceexceptNameError:fromfunctoolsimportreducedeflcm(a,b):mul=int.__mul__ifaandb:da=list(decompose(abs(a)))db=list(decompose(abs(b)))merge=dafordinda:ifdindb:db.remove(d)merge+=dbreturnreduce(mul,merge,1)return0if__name__=='__main__':print(lcm(12,18))# 36print(lcm(-6,14))# 42assertlcm(0,2)==lcm(2,0)==0
>>>deflcm(*values):values=set([abs(int(v))forvinvalues])ifvaluesand0notinvalues:n=n0=max(values)values.remove(n)whileany(n%mforminvalues):n+=n0returnnreturn0>>>lcm(-6,14)42>>>lcm(2,0)0>>>lcm(12,18)36>>>lcm(12,18,22)396>>>
>>>deflcm(p,q):p,q=abs(p),abs(q)m=p*qifnotm:return0whileTrue:p%=qifnotp:returnm//qq%=pifnotq:returnm//p>>>lcm(-6,14)42>>>lcm(12,18)36>>>lcm(2,0)0>>>
(define gcd A 0 -> A A B -> (gcd B (MOD A B)))(define lcm A B -> (/ (* A B) (gcd A B)))
[ [ 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 )
"%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 already has defined both lcm and gcd funtions:
#langracket(lcm3456);returns 60(lcm8108);returns 216(gcd8108);returns 4(gcd108216432);returns 108
(formerly Perl 6)This function is provided as an infix so that it can be used productively with various metaoperators.
say3lcm4;# infixsay [lcm]1..20;# reductionsay ~(1..10Xlcm1..10)# cross
122327925601 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
This is from the math extensions library included with Retro.
: gcd ( ab-n ) [ tuck mod dup ] while drop ;: lcm ( ab-n ) 2over gcd [ * ] dip / ;
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. */numericdigits10000/*can handle 10k decimal digit numbers.*/say'the LCM of 19 and 0 is ───► 'lcm(190)say'the LCM of 0 and 85 is ───► 'lcm(085)say'the LCM of 14 and -6 is ───► 'lcm(14,-6)say'the LCM of 18 and 12 is ───► 'lcm(1812)say'the LCM of 18 and 12 and -5 is ───► 'lcm(1812,-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-12**521-1)/* [↑] 7th & 13th Mersenne primes.*/exit/*stick a fork in it, we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/lcm:procedure;parsearg$,_;$=$_;doi=3toarg();$=$arg(i);end/*i*/parsevar$x$/*obtain the first value in args. */x=abs(x)/*use the absolute value of X. */dowhile$\==''/*process the remainder of args. */parsevar$!$;if!<0then!=-!/*pick off the next arg (ABS val).*/if!==0thenreturn0/*if zero, then LCM is also zero. */d=x*!/*calculate part of the LCM here. */dountil!==0;parsevaluex//!!with!xend/*until*//* [↑] this is a short & fast GCD*/x=d%x/*divide the pre─calculated value.*/end/*while*//* [↑] process subsequent args. */returnx/*return with the LCM of the args.*/
output when using the (internal) supplied list:
the LCM of 19 and 0 is ───► 0the LCM of 0 and 85 is ───► 0the LCM of 14 and -6 is ───► 42the LCM of 18 and 12 is ───► 36the LCM of 18 and 12 and -5 is ───► 180the LCM of 18 and 12 and -5 and 97 is ───► 17460the LCM of 2**19-1 and 2**521-1 is ───► 3599124170836896975638715824247986405702540425206233163175195063626010878994006898599180426323472024265381751210505324617708575722407440034562999570663839968526337
using different argument handling-
Use as lcm(a,b,c,---)
lcm2:procedurex=abs(arg(1))dok=2toarg()Whilex<>0y=abs(arg(k))x=x*y/gcd2(x,y)endreturnxgcd2:procedurex=abs(arg(1))doj=2toarg()y=abs(arg(j))Ify<>0ThenDodountilz==0z=x//yx=yy=zendendendreturnx
see lcm(24,36) func lcm m,n lcm = m*n / gcd(m,n) return lcmfunc gcd gcd, b while b c = gcd gcd = b b = c % b end return gcd
For unsigned integers
≪ DUP2 < ≪ SWAP ≫ IFTWHILE DUP B→RREPEAT SWAP OVER / LAST ROT * -END DROP ≫ 'GCD' STO≪ DUP2 * ROT ROTGCD /≫ 'LCM' STO#12d #18dLCM
1: #36d
For usual integers (floating point without decimal part)
≪WHILE DUPREPEAT SWAP OVER MODEND DROP ABS≫ 'GCD' STO≪ DUP2 * ROT ROTGCD /≫ 'LCM' STO
Ruby has anInteger#lcm method, which finds the least common multiple of two integers.
irb(main):001:0>12.lcm18=>36
I can also write my ownlcm method. This one takes any number of arguments.
defgcd(m,n)m,n=n,m%nuntiln.zero?m.absenddeflcm(*args)args.inject(1)do|m,n|return0ifn.zero?(m*n).abs/gcd(m,n)endendplcm12,18,22plcm15,14,-6,10,21
396210
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)endfunction lcm(m, n) lcm = abs(m * n) / GCD(m, n)end functionfunction GCD(a, b) while b c = a a = b b = c mod b wend GCD = abs(a)end function
This implementation uses a recursive implementation of Stein's algorithm to calculate the gcd.
usestd::cmp::{max,min};fngcd(a:usize,b:usize)->usize{match((a,b),(a&1,b&1)){((x,y),_)ifx==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!(),}}fnlcm(a:usize,b:usize)->usize{a*b/gcd(a,b)}fnmain(){println!("{}",lcm(6324,234))}
defgcd(a:Int,b:Int):Int=if(b==0)a.abselsegcd(b,a%b)deflcm(a:Int,b:Int)=(a*b).abs/gcd(a,b)
lcm(12,18)// 36lcm(2,0)// 0lcm(-6,14)// 42
>(definegcd(lambda(ab)(if(zero?b)a(gcdb(remainderab)))))>(definelcm(lambda(ab)(if(or(zero?a)(zero?b))0(abs(*b(floor(/a(gcdab))))))))>(lcm1218)36
$ 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]
function gcd m, nrepeat while m is greater than 0put m into tempput n modulo m into mput temp into nend repeatreturn nend gcdfunction lcm m, nreturn m divided by gcd(m, n) times nend lcm
Built-in:
sayMath.lcm(1001,221)
Using GCD:
funcgcd(a,b){while(a){(a,b)=(b%a,a)}returnb}funclcm(a,b){(a&&b)?(a/gcd(a,b)*b):0}saylcm(1001,221)
17017
Smalltalk has a built-inlcm method onSmallInteger:
12lcm:18
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);}fungcd(0,n)=n|gcd(m,n)=gcd(nmodm,m)funlcm(m,n)=abs(x*y)divgcd(m,n)
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)
Using the Swift GCD function.
func lcm(a:Int, b:Int) -> Int { return abs(a * b) / gcd_rec(a, b)}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
lcm(12,18 36
// 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 ) ) //ENDPROC 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 FALSEEND
$ txr -p '(lcm (expt 2 123) (expt 6 49) 17)'43259338018880832376582582128138484281161556655442781051813888
// Least common multiplefunction 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)}`);LCM(35, 21) = 105
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@ LoopReturn (ABS(a@))_LCM Param(2)If a@*b@ Return (ABS(a@*b@)/FUNC(_GCD_Iterative_Euclid(a@,b@)))Else Return (0)EndIf
LCM of 12 : 18 = 360 OK, 0:330
# Greatest Common Divisor using Euclidean algorithmGcd ← ⊙◌⍢(⟜◿:|±,)# Least Common MultipleLcm ← ÷⊃(Gcd|⌵×)
gcd() {# Calculate $1 % $2 until $2 becomes zero.until test 0 -eq "$2"; do# Parallel assignment: set -- 1 2set -- "$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# => 210alias 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 -42echo $result# => 210
import "math"out (lcm 12 18) endl console
36
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(){ inta = 12; intb = 18; stdout.printf("lcm(%d, %d) = %d\n",a, b, lcm(a, b));}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 = uEnd FunctionFunction lcm(m As Long, n As Long) As Long lcm = Abs(m * n) / gcd(m, n)End Function
Function LCM(a,b)LCM = POS((a * b)/GCD(a,b))End FunctionFunction GCD(a,b)DoIf a Mod b > 0 Thenc = a Mod ba = bb = cElseGCD = bExit DoEnd IfLoopEnd FunctionFunction POS(n)If n < 0 ThenPOS = n * -1ElsePOS = nEnd IfEnd Functioni = WScript.Arguments(0)j = WScript.Arguments(1)WScript.StdOut.Write "The LCM of " & i & " and " & j & " is " & LCM(i,j) & "."WScript.StdOut.WriteLine
C:\>cscript /nologo lcm.vbs 12 18The LCM of 12 and 18 is 36.C:\>cscript /nologo lcm.vbs 14 -6The LCM of 14 and -6 is 42.C:\>cscript /nologo lcm.vbs 0 35The LCM of 0 and 35 is 0.C:\>
Operator
@lcm a b
Number expression
!#~km a b
Function (using gcd)
&[a b] *b /a @gcd a b
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]))")}lcm(12, 18) = 36lcm(-6, 14) = 42lcm(35, 0) = 0
' Least common multiplePROGRAM "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 FUNCTIONFUNCTION Gcd(m&, n&) DO WHILE m& <> 0 tmp& = m& m& = n& MOD m& n& = tmp& LOOP RETURN n&END FUNCTIONFUNCTION Lcm(m&, n&) RETURN m& / Gcd(m&, n&) * n&END FUNCTIONEND PROGRAM
LCM(35, 21) = 105
include c:\cxpl\codes;func GCD(M,N); \Return the greatest common divisor of M and Nint 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 multipleint M, N;return abs(M*N) / GCD(M,N);\Display the LCM of two integers entered on command lineIntOut(0, LCM(IntIn(8), IntIn(8)))
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 uend subsub lcm(m, n) return m / gcd(m, n) * nend subprint "Least common multiple: ", lcm(12345, 23044)
fcn lcm(m,n){ (m*n).abs()/m.gcd(n) } // gcd is a number methodzkl: lcm(12,18)36zkl: lcm(-6,14)42zkl: lcm(35,0)0