gcd.pro

/* два натуральных числа называются взаимно простыми, если они имеют в точности один общий делитель. Пара натуральных чисел (х,у) задается списком (х.у.nil). Две пары чисел, отличающиеся лишь порядком следования чисел, считаются одинаковыми. Составить логическую программу, которая для заданного натурального числа N вычисляет список Х всех неодинаковых пар взаимно простых чисел, не превосходящих N. Запрос G(N,X) */

gcd( A, B, X ) :- A =:= B, !, X is A.
gcd( A, B, X ) :- A > B, !, T is (A-B), gcd( T, B, X ).
gcd( A, B, X ) :- T is (B-A), gcd( T, A, X ).

vp( A, B ) :- gcd( A, B, X ), X =:= 1.

build_vp( A, _, [] ) :- A =:= 0, !.
build_vp( A, B, Remain ) :- B =:= 0, !, T is (A-1), build_vp( T, T, Remain ).
build_vp( A, B, [ [ A, B ] | Remain ] ) :- vp( A, B ), !, T is (B-1), build_vp( A, T, Remain ).
build_vp( A, B, Remain ) :- T is (B-1), build_vp( A, T, Remain ).

g( N, X ) :- build_vp( N, N, X ).