Существует другая версия алгоритма Евклида, в которой операция вычитания заменяется операцией вычисления остатка.
Эта версия в наши дни считается предпочтительней, так как содержит в себе, в среднем, ощутимо меньшее количество шагов. Тем не менее, во времена, когда компьютеры были большие и медленные, операция деления могла быть сама по себе сложной процедурой. И тогда первая версия алгоритма могла оказаться эффективней.
Реализуйте алгоритма Евклида, заменив операцию вычитания операцией вычисления остатка от деления.
Даны два натуральных числа
A и
B. Напишите функцию
nod(A, B), которая возвращает наибольший общий делитель чисел
A и
B.
Примеры работы программы
| № |
Входные данные |
Выходные данные |
| 1 |
12 42 |
6 |
Помните, что в решении нельзя использовать циклы.
От Вас требуется написать только функцию, ничего вводить и выводить не нужно!Запрещенные операторы: for; while; do; until; gcd