Greatest Common Divisor
/* 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 is abs(X), Y1 is abs(Y), gcd_1(X1, Y1, Z).
gcd_1(X, 0, Z):-!, Z = X.
gcd_1(X, Y, Z):-R is 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 is (X * Y) // 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 is U3 // V3,
W3 is U3 mod V3,
W2 is U2 - V2 * Q,
W1 is 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).
LPA Index
Home Page