Problem Statement

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   for greatest common divisor,   then this formula calculates   lcm.

One can also find   lcm   by merging the prime decompositions of both   m   and   n.

Let's start with the solution:

: 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