Ответ в теме: Наибольший общий делитель на Prolog

      Комментарии к записи Ответ в теме: Наибольший общий делитель на Prolog отключены
#2059

Самый простой алгоритм вычисления наибольшего общего делителя двух чисел заключается в последовательном переборе всех возможных делителей в порядке убывания и их проверке. Первое число, оказавшееся делителем возвращается в качестве результата. Нижней границей перебора в любом случае окажется единица, верхней — одно из двух исходных чисел. Блок-схема такого алгоритма прикреплена.
В качестве начального значения верхней границы может передаваться, наименьшее из двух исходных чисел, но на асимптотическую эффективность алгоритма это не окажет влияния. Вызов функции и инициализацию верхнего значения удобно вынести в отдельную функцию еще и потому, что в ней же возможно вычисление модулей чисел (приведенный алгоритм сработает только для положительных чисел).
Реализация поиска наибольшего общего делителя на SWI Prolog:

greatest_common_denominator(A, B, Denominator):-
  greatest_common_denominator(A, B, A, Denominator).
  
greatest_common_denominator(A, B, Iterator, Iterator):-
  0 is A mod Iterator, 0 is B mod Iterator, !.
greatest_common_denominator(A, B, Iterator, Denominator):-
  NextIterator is Iterator - 1,
  greatest_common_denominator(A, B, NextIterator, Denominator).