Дональд Кнут, автор трактата “
Искусство программирования”, считает алгоритм Евклида первым в истории. Потому что, не смотря на то, что алгоритм был придуман и использовался еще до
Евклида, который жил в IV-III вв. до нашей эры (он упоминается уже у
Аристотеля, жившего веком ранее), Евклид описывает процесс итеративно, что согласуется с современным значением слова "алгоритм".
"Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД."
Сам же алгоритм Евклида знаком любым современным школьникам. Математическое описание можно посмотреть
здесь. Реализуйте
классический алгоритм Евклида и оформите его в виде функции
nod(a, b)
, которая принимает на вход 2 числа и возвращает наибольший общий делитель двух этих чисел.
Ничего вводить и выводить не нужно! Вам необходимо только реализовать функцию.
Запрещенные операторы: gcd
; %