Записать алгоритм нахождения наибольшего общего делителя двух натуральных чисел.

Описание алгоритма нахождения НОД делением

1 - Большее число делим на меньшее.

2 - Если делится без остатка, то меньшее число и есть НОД.

3 - Если есть остаток, то большее число заменяем на остаток от деления.

4 - Переходим к пункту 1.

Пример такой:

Найти НОД для 30 и 18.

30/18 = 1 (остаток 12)

18/12 = 1 (остаток 6)

12/6 = 2 (остаток 0). Конец: НОД - это делитель. НОД (30, 18) = 6