Алгоритм Евклида: наибольший общий делитель

Коротко: Очень старый быстрый метод вычисления наибольшего общего делителя (НОД) двух чисел многократным делением с остатком.

Подробнее: НОД 48 и 18 равен 6 — наибольшее число, делящее оба. Вместо перечисления всех делителей Евклид (около 300 до н. э.) использует наблюдение: НОД(a, b) = НОД(b, a mod b). Пару заменяют на (b, остаток) и повторяют, пока остаток не станет 0. Последнее ненулевое число — НОД.

Подробности

Пример

НОД(48, 18):

48 mod 18 = 12

См. также: рекурсия, О-нотация, алгоритмы