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

Алгоритм Евклида заключается в следующем: 1

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

Ещё один вариант алгоритма Евклида — с вычитанием: 1

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