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!

About these ads

2 thoughts on “Prolog program to find GCDs and LCMs

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s