# Prolog program to find GCDs and LCMs

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,

1. with 2 arguments, the input numbers
2. 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)
lcm(num,num,result)
gcd(num,num)
gcd(num,num,result)

clauses

lcm(X1,X2):-
lcm(X1,X2,Y),write(Y),nl.
lcm(X1,X2,Y):-
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!

## 2 thoughts on “Prolog program to find GCDs and LCMs”

1. xaxioza says:

It’s cool guys
Nice to see u

Like

This site uses Akismet to reduce spam. Learn how your comment data is processed.