The **least common multiple (LCM)** of two integers *a*, *b* is the smallest positive integer that is a multiple of both* a* and *b*.

Despite of the fact, there exist several formulas to calculate the LCM of two integers, most popular formula, especially to the programmers, is by using GCD of the two:

*LCM(a, b) = a*b/ GCD(a,b)*

Therefore, we need to focus on calculating GCD before we do LCM.

**Greatest Common Divisor (gcd) **of two or more non-zero integers is the largest positive integer that divides the numbers without a remainder.

For sake of simplicity, we will reduce GCD function to take two arguments in decreasing order, i.e. *a*>=*b*.

Now only for the users ease, we will handle the opposite case (a<b) by swapping the arguments and calling GCD(b,a).

Other cases to be handled, include, *a=b*, *b=0 *and *a<b.*

- if
*a=b*, then GCD is also same (b). - If
*b=0*, (here it is the base case of recursion), GCD is a - Else,
*GCD(a,b)=GCD(b,c)*, where*c=a modulo b*

To handle predicates with care, we use two type of gcd,

- with 2 arguments, the input numbers
- with 3 arguments, 2 inputs and one result (GCD)

Likewise, lcm also has two overloads for the same reason.

Henceforth, I may hereby present a code devised for the very course by the lazy brain of mine below:

`domains`

`num,result=`

`integer`

predicates

lcm(num,num,result)

gcd(num,num)

gcd(num,num,result)

clauses

lcm(X1,X2,Y),write(Y),nl.

gcd(X1,X2,Y1),Y=X1*X2/Y1.

gcd(X1,X2):-

gcd(X1,X2,Y),write(Y),nl.

gcd(X1,0,Y):-

Y=X1.

gcd(X1,X2,Y):-

X1=X2,Y=X2.

gcd(X1,X2,Y):-

X1<X2,gcd(X2,X1,Y).

gcd(X1,X2,Y):-

X3=X1 mod X2, gcd(X2,X3,Y).

Happy Prolog!

It’s cool guys

Nice to see u

LikeLike

[…] Read more: Prolog program to find GCDs and LCMs « inside the insight […]

LikeLike