Greatest Common Divisor
check_determ
domains
int = integer
ints = int*
predicates
gcd(int,int,int)
gcd_1(int,int,int)
lcm(int,int,int)
gcd_extended(int,int,int,int,int)
gcd_extended_1(int,int,int,int,int,int,int,int,int)
are_relatively_prime(ints)
are_relatively_prime_1(ints,int)
clauses
/* gcd(X, Y, Z) is true if Z is the greatest common divisor of X and Y. */
/* e.g. gcd(24140, 16762, 34). */
gcd(X, 0, X):-!.
gcd(X, Y, Z):-X1 = abs(X), Y1 = abs(Y), gcd_1(X1, Y1, Z).
gcd_1(X, 0, X):-!.
gcd_1(X, Y, Z):-R = X mod Y, gcd_1(Y, R, Z).
/* lcm(X, Y, Z) is true if Z is the lowest common multiple of X and Y. */
/* e.g. lcm(35, 45, 315). */
lcm(X, Y, Z):-gcd(X, Y, T), Z = (X * Y) div T.
/* gcd_extended(X, Y, U1, U2, Z) is true if X*U1 + Y*U2 = Z = gcd(X, Y). */
/* e.g. gcd_extended(24140, 16762, -234, 337, 34). */
gcd_extended(X, Y, U1, U2, Z):-
gcd_extended_1(Y, 1, 0, X, 0, 1, Z, U2, U1).
gcd_extended_1(0, _, _, U3, U2, U1, U3, U2, U1):-!.
gcd_extended_1(V3, V2, V1, U3, U2, U1, U3P, U2P, U1P):-
Q = U3 div V3,
W3 = U3 mod V3,
W2 = U2 - V2 * Q,
W1 = U1 - V1 * Q,
gcd_extended_1(W3, W2, W1, V3, V2, V1, U3P, U2P, U1P).
/* are_relatively_prime(Xs) is true if the elements of Xs are relatively */
/* prime to each other in pairs. */
/* e.g. are_relatively_prime([6, 35, 143]) is true. */
are_relatively_prime([]).
are_relatively_prime([X|Xs]):-
are_relatively_prime_1(Xs, X),
are_relatively_prime(Xs).
are_relatively_prime_1([], _).
are_relatively_prime_1([X2|Xs], X1):-
gcd(X1, X2, 1),
are_relatively_prime_1(Xs, X1).
Turbo Prolog Index
Home Page