Great Common Divisor

Posted on | Post modified | In ,

Write the greatest common divisor (GCD) program in Prolog. The greatest common divisor of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
% base case
gcd(0, X, X):-
    X > 0, !.

gcd(X, Y, Z):-
    X >= Y, !,
    X1 is X-Y,
    gcd(X1,Y,Z).
gcd(X, Y, Z):- 
    X1 is Y-X,
    gcd(X1,X,Z).

gcd([H],H). 
gcd([H1,H2|T], D) :-
	gcd(H1, H2, D2),
	gcd([D2|T], D).

% Testing it:
test1 :-
	gcd([5,4,3,7], X),
	write(X),
	nl,
	fail;
	true.

?- test1.