Least common multiple: Difference between revisions
added ocaml |
|||
Line 399: | Line 399: | ||
end function |
end function |
||
</lang> |
</lang> |
||
=={{header|Logo}}== |
|||
<lang logo>to abs :n |
|||
output sqrt product :n :n |
|||
end |
|||
to gcd :m :n |
|||
output ifelse :n = 0 [ :m ] [ gcd :n modulo :m :n ] |
|||
end |
|||
to lcm :m :n |
|||
output quotient (abs product :m :n) gcd :m :n |
|||
end</lang> |
|||
=={{header|Lua}}== |
=={{header|Lua}}== |
Revision as of 22:23, 15 August 2011
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
You are encouraged to solve this task according to the task description, using any language you may know.
Compute the least common multiple of two integers.
Given m and n, the least common multiple is the smallest positive integer that has both m and n as factors. For example, the least common multiple of 12 and 18 is 36, because 12 is a factor (12 × 3 = 36), and 18 is a factor (18 × 2 = 36), and there is no positive integer less than 36 that has both factors. As a special case, if either m or n is zero, then the least common multiple is zero.
One way to calculate the least common multiple is to iterate all the multiples of m, until you find one that is also a multiple of n.
If you already have gcd for greatest common divisor, then this formula calculates lcm.
One can also find lcm by merging the prime decompositions of both m and n.
References: MathWorld, Wikipedia.
Ada
lcm_test.adb: <lang Ada>with Ada.Text_IO; use Ada.Text_IO;
procedure Lcm_Test is
function Gcd (A, B : Integer) return Integer is M : Integer := A; N : Integer := B; T : Integer; begin while N /= 0 loop T := M; M := N; N := T mod N; end loop; return M; end Gcd;
function Lcm (A, B : Integer) return Integer is begin if A = 0 or B = 0 then return 0; end if; return abs (A * B) / Gcd (A, B); end Lcm;
begin
Put_Line ("LCM of 12, 18 is" & Integer'Image (Lcm (12, 18))); Put_Line ("LCM of -6, 14 is" & Integer'Image (Lcm (-6, 14))); Put_Line ("LCM of 35, 0 is" & Integer'Image (Lcm (35, 0)));
end Lcm_Test;</lang>
Output:
LCM of 12, 18 is 36 LCM of -6, 14 is 42 LCM of 35, 0 is 0
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>
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
BBC BASIC
Template:Workswith BBC BASIC for Windows <lang BBC BASIC>
DEF FN_LCM(M%,N%) IF M%=0 OR N%=0 THEN =0 ELSE =ABS(M%*N%)/FN_GCD_Iterative_Euclid(M%, N%) DEF FN_GCD_Iterative_Euclid(A%, B%) LOCAL C% WHILE B% C% = A% A% = B% B% = C% MOD B% ENDWHILE = ABS(A%)
</lang>
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>
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 csharp>public static int Lcm(int m, int n)
{ int r = 0; Func<int, int, int> gcd = delegate(int m2, int n2) { while (n2!=0) { var t2 = m2; m2 = n2; n2 = t2%n2; } return m2; }; try { if (m == 0 || n == 0) throw new ArgumentException(); r = Math.Abs(m*n)/gcd(m, n); } catch(Exception exception) { Console.WriteLine(exception.Message); } return (r<0) ? -r : r; }</lang>
Clojure
<lang Clojure>(defn gcd [a b] (if (zero? b) a (recur b, (mod a b))))
(defn lcm [a b] (/ (* a b) (gcd a b)))</lang>
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;
T lcm(T)(T m, T n) {
if (m == 0) return m; if (n == 0) return n; T r = (m * n) / gcd(m, n); return (r < 0) ? -r : r;
}
T gcd(T)(T a, T b) {
while (b != 0) { auto t = b; b = a % b; a = t; } return a;
}
void main() {
writeln(lcm(12, 18)); writeln(lcm(BigInt("2562047788015215500854906332309589561"), BigInt("6795454494268282920431565661684282819")));
}</lang> Output:
36 15669251240038298262232125175172002594731206081193527869
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>
Frink
Frink has a built-in LCM function that handles arbitrarily-large integers. <lang frink> println[lcm[2562047788015215500854906332309589561, 6795454494268282920431565661684282819]] </lang>
GAP
<lang gap># Built-in LcmInt(12, 18);
- 36</lang>
Go
<lang go>package main
import (
"big" "fmt"
)
var m,n big.Int
func init() {
m.SetString("2562047788015215500854906332309589561", 10) n.SetString("6795454494268282920431565661684282819", 10)
}
func main() {
var d big.Int big.GcdInt(&d, nil, nil, &m, &n) fmt.Println(d.Mul(d.Div(&m, &d), &n))
}</lang> Output:
15669251240038298262232125175172002594731206081193527869
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 boolean arguments (0 and 1) it is equivalent to "and"
0 0 0 1
*./~ 0 1
0 0 0 1</lang>
Java
<lang java>
import java.util.Scanner;
public class LeastCommonMultiple { public static void main(String[] args) { Scanner aScanner = new Scanner(System.in);//allows user input int m, n, leastCommonMultiple; //prompts user for values to find the LCM for, then saves them to m and n System.out.print("Enter the value of m:"); m = aScanner.nextInt(); System.out.print("Enter the value of n:"); n = aScanner.nextInt(); int multipleOfM = m, multipleOfN = n; /* this section increases the value of multipleOfM until it is greater / than or equal to the multipleOfN, then does it again when the lesser / becomes the greater--if they aren't equal*/ if (m != n) { for ( ; multipleOfM != multipleOfN ; ) { if (multipleOfM < multipleOfN) { for ( int i = 0; multipleOfM < multipleOfN; i++) { multipleOfM = m * i; } } else { for (int i = 0; multipleOfN < multipleOfM; i++) { multipleOfN = n * i; } } } leastCommonMultiple = multipleOfN;//equals multpleOfM } else { leastCommonMultiple = m; } System.out.println("Least Common Multiple of " + m + " and " + n + " is: " + leastCommonMultiple); } }
</lang>
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>
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>
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>
PARI/GP
Built-in function: <lang parigp>lcm</lang>
Perl 6
This function is provided as an infix so that it can be used productively with various metaoperators. <lang>say 3 lcm 4; # infix say [lcm] 1..20; # reduction say ~(1..10 Xlcm 1..10) # cross</lang> Output:
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
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>
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> import operator from prime_decomposition import decompose
def lcm(a, b):
if a and b: da = list(decompose(abs(a))) db = list(decompose(abs(b))) merge= da for d in da: if d in db: db.remove(d) merge += db return reduce(operator.mul, merge, 1) return 0
if __name__ == '__main__':
print( lcm(12, 18) ) # 36 print( lcm(-6, 14) ) # 42 assert lcm(0, 2) == lcm(2, 0) == 0</lang>
Iteration over multiples
<lang python>>>> def lcm(*values): values = set([abs(int(v)) for v in values]) if values and 0 not in values: n = n0 = max(values) values.remove(n) while any( n % m for m in values ): n += n0 return n return 0
>>> lcm(-6, 14) 42 >>> lcm(2, 0) 0 >>> lcm(12, 18) 36 >>> lcm(12, 18, 22) 396 >>> </lang>
Repeated modulo
<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>
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>
Ruby
Ruby has an Integer#lcm method, which finds the least common multiple of two integers.
<lang ruby>irb(main):001:0> require 'rational' => true irb(main):002:0> 12.lcm 18 => 36</lang>
I can also write my own lcm method. This one takes any number of arguments, and works by iterating the multiples of m until it finds a multiple of n.
<lang ruby>def lcm(*args)
args.inject(1) do |m, n| next 0 if m == 0 or n == 0 i = m loop do break i if i % n == 0 i += m end end
end</lang>
<lang ruby>irb(main):004:0> lcm 12, 18 => 36 irb(main):005:0> lcm 12, 18, 22 => 396</lang>
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: result is 0; local var integer: help is 0; begin while a <> 0 do help := b rem a; b := a; a := help; end while; result := b; end func;
const func integer: lcm (in integer: a, in integer: b) is
return a div gcd(a, b) * b;
const proc: main is func
begin writeln("lcm(35, 21) = " <& lcm(21, 35)); end func;</lang>
Original source: [1]
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 ti83basic>lcm(12, 18)
36</lang>