Пример нахождения НОД (наименьшего общего делителя) для двух чисел с помощью алгоритма Евклида.

Суть алгоритма достаточно простая, вычитаем из большего числа меньшее. Затем берем разницу и вычитаемое число, выбираем из них большее число. И далее из большего числа вычитаем меньшее. Повторяем это до тех пор, пока разница не сравняется с вычитаемым. Этои будт НОД(наибольший общий делитель). Подробнее читать тут: