EMZETT.Алгоритм Евкліда: найбільший спільний дільник
Коротко: Дуже давній швидкий метод обчислення найбільшого спільного дільника (НСД) двох чисел багаторазовим діленням із остачею.
Докладніше: НСД 48 і 18 дорівнює 6 — найбільше число, що ділить обидва. Замість перелічування всіх дільників Евклід (близько 300 до н. е.) використовує спостереження: НСД(a, b) = НСД(b, a mod b). Пару замінюють на (b, остача) і повторюють, доки остача не стане 0. Останнє ненульове число — НСД.
Подробиці
Приклад
НСД(48, 18):
48 mod 18 = 12