Взаимно простые числа на Prolog

      Комментарии к записи Взаимно простые числа на Prolog отключены

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 1 неделя, 2 дн. назад.

  • Автор
    Сообщения
  • #3920

    Нужно написать на языке Prolog программу, проверяющую являются ли два введенных числа взаимно простыми.

    Числа A и B называются взаимно простыми в случае, если они не имеют общих делителей кроме +-1. Примитивный (простой, но неэффективный) алгоритм проверки чисел на взаимную простоту мог бы заключаться в переборе всех чисел i = 2, 3, .. min(A,B)-1 и проверки что A mod i = B mod i = 0.

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

    co_primes(A, B):-
      greatest_common_divisor(A, B, 1).

    Результаты работы функции приведены на скриншоте:

Для ответа в этой теме необходимо авторизоваться.