Что такое алгоритм Евклида?
Алгоритм Евклида — один из самых древних известных алгоритмов: его описал греческий математик Евклид около 300 года до н. э. Он находит наибольший общий делитель (НОД) двух целых чисел — то есть самое большое число, на которое оба делятся без остатка. Наш калькулятор применяет этот алгоритм к любым двум неотрицательным целым числам, а заодно вычисляет их наименьшее общее кратное (НОК).
Как пользоваться калькулятором
Введите два числа в поля a и b и нажмите кнопку расчёта. В качестве основного результата вы получите НОД, а дополнительно — НОК. Порядок чисел не важен: НОД(48, 36) равен НОД(36, 48). Отрицательные значения берутся по модулю, а если одно из чисел равно 0, то НОД совпадает со вторым числом.
Разбор формулы
В основе алгоритма лежит простая идея: любой общий делитель чисел a и b делит и их остаток a mod b. Поэтому мы раз за разом заменяем большее число остатком от деления:
$$\gcd(a,b) = \gcd(b,\, a \bmod b), \quad \gcd(a,0) = a$$
На каждом шаге числа быстро уменьшаются, поэтому даже огромные значения сходятся за считаные итерации. НОК затем находится по формуле $$\operatorname{lcm}(a,b) = \dfrac{a \times b}{\gcd(a,b)}$$
Разбор примера
Найдём \(\gcd(48, 36)\):
$$48 \bmod 36 = 12 \rightarrow \gcd(36, 12)$$
$$36 \bmod 12 = 0 \rightarrow \gcd(12, 0) = \mathbf{12}$$
Итак, НОД равен 12, а НОК \(= \dfrac{48 \times 36}{12} = \dfrac{1728}{12} = \mathbf{144}\).
Частые вопросы
А если оба числа равны 0? НОД нуля и нуля здесь принимается равным 0, и НОК тоже равен 0, поскольку положительного кратного не существует.
Почему это быстрее, чем перебирать делители? Вместо поиска всех делителей алгоритм использует трюк с остатком, резко сокращая размер задачи на каждом шаге — обычно за логарифмическое время.
Справится ли он с очень большими числами? Да. Алгоритм Евклида эффективен даже для многозначных чисел: ему нужно лишь небольшое количество операций взятия остатка.
