/* 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).