Алгоритм Евклида — это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел. 3

Суть алгоритма заключается в последовательном делении: 2

1. Большее число делят на меньшее. 12
2. Меньшее число делят на остаток, который получается после деления. 1
3. Первый остаток делят на второй остаток. 1
4. Второй остаток делят на третий и т. д.. 1
5. Деление продолжается до тех пор, пока в остатке не получится нуль. 1 Последний делитель и есть наибольший общий делитель. 1

Ещё один вариант алгоритма Евклида с использованием операции вычитания: 5

1. Из большего числа вычитают меньшее. 3
2. Если получается 0, значит, числа равны друг другу и являются НОД (следует выйти из цикла). 3
3. Если результат вычитания не равен 0, то большее число заменяют на результат вычитания и переходят к пункту 1. 3