Алгоритм Евкліда
Матеріал з Вікіпедії — вільної енциклопедії.
В елементарній математиці алгоритм Евкліда — це алгоритм обчислення найбільшого спільного дільника (НСД) двох натуральних чисел. Алгоритм не використовує розкладу чисел на прості множники, а базується на залежності
- НСД(a, b)= НСД(b, a mod b),
де a mod b означає остачу від ділення a на b.
Алгоритм можна також використовувати для знаходження НСД в інших структурах, які допускають обчислення залишку від ділення елементів, наприклад, у кільці многочленів над довільним полем, кільці гаусових цілих чисел, тощо.
Зміст |
[ред.] Історія
Алгоритм Евкліда є одним з найстарших алгоритмів. Правдоподібно, автором алгоритму є Евдокс Кнідський, а Евклід лише використав його у своїх Елементах. Евклід сформулював геометричну задачу знаходження найбільшої спільної «міри» двох довжин. Алгоритм розв'язку передбачав повторювання віднімання довжини коротшого відрізка від довжини довшого.
[ред.] Опис алгоритму
Маючи два натуральні числа a та b:
- якщо b=0, то a є шуканим НСД,
- інакше повторюємо обчислення для пари b та залишку від ділення a на b (тобто a mod b).
[ред.] Псевдокод
Версія ітераційна:
НСД( a, b)
поки b ≠ 0
c := остача від ділення a на b
a := b
b := c
поверни a
Версія рекурсивна:
НСД( a, b)
якщо b = 0
поверни a
інакше
поверни НСД( b, остача від ділення a на b)
[ред.] Приклад
Обчислимо НСД чисел 1071 та 1029.
| a | b | Пояснення | ||
| НСД( | 1071, | 1029) | Початкові аргументи | |
| = | НСД( | 1029, | 42) | 1071 mod 1029 = 42 |
| = | НСД( | 42, | 21) | 1029 mod 42 = 21 |
| = | НСД( | 21, | 0) | 42 mod 21 = 0 |
| = | 21 | Оскільки b=0, то повертаємо a=21 |
У випадку невеликих чисел, можна використати послідовне ділення у стовпчик. Наприклад, нам потрібно знайти НСД (2700, 1520):
Отже, НСД (2700, 1520) = 20.
