Як за допомогою Евклідового алгоритму знайти найбільший спільний дільник (GCD)

Для цієї теми спочатку ви повинні знати про Найбільший спільний дільник (GCD) та операцію MOD.

Найбільший спільний дільник (GCD)

GCD з двох або більше цілих чисел - це найбільше ціле число, яке ділить кожне з цілих чисел таким чином, що їх залишок дорівнює нулю.

Ось приклад:

GCD 20, 30 = 10 (10 - найбільше число, яке ділить 20 і 30 із залишком 0)

GCD 42, 120, 285 = 3 (3 - найбільше число, яке ділить 42, 120 і 285 із залишком 0)

Операція “мод”

Операція мода дає вам залишок, коли два натуральні числа розділені. Ми пишемо це так:

A mod B = R

Це означає, що ділення A на B дає вам залишок R. Це інакше, ніж ваша операція ділення, яка дає вам фактор.

Ось приклад:

7 мод 2 = 1 (ділення 7 на 2 дає залишок 1)

42 mod 7 = 0 (ділення 42 на 7 дає залишок 0)

Якщо ви зрозумієте дві наведені вище концепції, ви легко зрозумієте евклідівський алгоритм.

Евклідовий алгоритм найбільшого спільного дільника (GCD)

Євклідівський алгоритм знаходить GCD з 2 чисел.

Ви краще зрозумієте цей алгоритм, побачивши його в дії. Припускаючи, що ви хочете обчислити GCD 1220 та 516, давайте застосуємо евклідовий алгоритм.

Псевдокодекс алгоритму:

Крок 1: Нехай a, bбудуть два числа

Крок 2: a mod b = R

Крок 3: Нехай a = bіb = R

Крок 4: Повторюйте кроки 2 і 3, поки a mod bне перевищить 0

Крок 5: GCD = b

Крок 6: Готово

Ось код Javascript для виконання GCD:

function gcd(a, b) { var R; while ((a % b) > 0) { R = a % b; a = b; b = R; } return b; }

Ось код Javascript для виконання GCD за допомогою рекурсії:

function gcd(a, b) { if (b == 0) return a; else return gcd(b, (a % b)); }

Ви також можете скористатися Евклідовим алгоритмом, щоб знайти GCD більше двох чисел. Оскільки GCD є асоціативним, діє наступна операція:  GCD(a,b,c) == GCD(GCD(a,b), c)

Обчисліть GCD перших двох чисел, потім знайдіть GCD результату та наступне число. Приклад:GCD(203,91,77) == GCD(GCD(203,91),77) == GCD(7, 77) == 7

Ви можете знайти GCD nчисел таким же чином.