Least common multiple
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.
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
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>
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.
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>
Prolog
SWI-Prolog knows gcd. <lang Prolog>lcm(0, _, 0) :- !.
lcm(_, 0, 0) :- !.
lcm(X, Y, Z) :- Z is X * Y / gcd(X,Y). </lang> Example :
?- lcm(18,12, Z). Z = 36.
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>
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>
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>