Алгоритъм на Евклид

Алгоритъмът на Евклид е алгоритъм за намиране на най-големия общ делител (НОД) на две естествени числа. Той е един от първите публикувани алгоритми. Описан е в книгата на Евклид „Елементи“ около 300 г. пр.н.е.

Теория

Нека $a$ и $b$ са естествени числа и редицата

$a,\, b,\,r_1 > r_2 > r_3 > r_4 > \cdots >r_n$

е определена така, че всяко $r_k$ е остатък от делението на пред-предния член на предния член, т. е.

$a = bq_0 + r_1$

$b = r_1q_1 + r_2$

$r_1 = r_2q_2 + r_3$

$\cdots$

$r_{n-1} = r_nq_n$

Тогава $(a,b)$ - най-големият общ делител на $a$ и $b$, е равен на $r_n$ - последния ненулев член на редицата.

Верността на алгоритъма следва от съжденията:

• Нека $a = bq + r$, тогава $(a,b)=(b,r).$
• $(0,r)=r.$ за всяко ненулево $r.$

Запис с думи

Взимайки двете дадени на входа на алгоритъма числа a и b, провери дали b е равно на 0.

Ако да, числото a е търсеният най-голям общ делител.

Ако не, повтори процеса, като използваш за входни данни b и остатъка, получен при деленето a на b (означаван по-долу с a mod b)

Рекурсивен запис

Пример на езика C (операторът x % y изчислява остатъка при деление x на y).

int gcd(int x, int y)
{
     if (y != 0)
          return x;
     else
          return gcd(y, x % y);
}

Процедурен запис

function gcd(a, b)
  while b!= 0
    var t := b
    b := a mod b
    a := t
  return a

Без използване на деление

function gcd(a, b)
  while a ≠ b
    if a > b
  while a = b
      a := a - b
    else
      b := b - a
  return a

Пример

Най-големият общ делител на числата 1071 и 1029 се пресмята по следния начин:

$1071 = 1 \cdot 1029 + 42$

$1029 = 24 \cdot 42 + 21$

$42 = 2 \cdot 21 + 0$

Следователно търсеният делител е 21.