Описание алгоритма нахождения НОД делением
Найти НОД для 30 и 18.
30/18 = 1 (остаток 12)
18/12 = 1 (остаток 6)
12/6 = 2 (остаток 0). Последний делитель и есть НОД: НОД (30, 18) = 6
Программа на языке Python
a = int(input(‘Введите первое число: ’))
b = int(input(‘Введите второе число: ’))
while a != 0 and b!=0:
if a > b:
a = a % b
else:
b = b % a
print (a+b)
Примечание. В цикле остаток, полученный при делении, присваивается переменным a или b. Если остаток равен нулю (мы не знаем, он в a или в b, поэтому проверяем оба условия), то цикл завершается. В конце, так как не известно, какой переменной присвоен НОД, на выход выдается сумма a и b (одно из переменных всегда будет равно 0 и не окажет влияния на сумму).