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

### от Уикипедия, свободната енциклопедия

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

## [редактиране] Алгоритъм на Евклид (теория)

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

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

  a = b q0 + r1
  b = r1q1 + r2
  r1 = r2q2 + r3
  rn - 1 = rnqn

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

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

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

## [редактиране] Алгоритъмът (запис с думи)

  Взимайки двете дадени на входа на алгоритъма числа a и b, провери дали b е равно на 0.
    Ако да, числото a е търсеният най-голям общ делител.
    Ако не, повтори процеса, като използваш за входни данни b и остатъка, получен при деленето a на b (означаван по-долу с a mod b)

## [редактиране] Рекурсивен запис

    function gcd(a, b)
      if b = 0
         return a
      else
         return gcd(b, a mod b);

## [редактиране] Процедурен запис

    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
          a := a - b
        else
          b := b - a
      return a

## [редактиране] Пример

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

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

## [редактиране] Виж още

Взето от „http://bg.wikipedia.org../../../%D0%B0/%D0%BB/%D0%B3/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D1%8A%D0%BC_%D0%BD%D0%B0_%D0%95%D0%B2%D0%BA%D0%BB%D0%B8%D0%B4_873c.html“.

Категории: Алгоритми | Теория на числата

##### Views

- Статия
- Беседа
- Текуща версия

##### Търсене

##### На други езици

- العربية
- Català
- Česky
- Deutsch
- English
- Español
- Suomi
- Français
- Magyar
- Bahasa Indonesia
- Italiano
- 日本語
- 한국어
- Lietuvių
- Latviešu
- Nederlands
- Polski
- Português
- Русский
- Slovenščina
- Svenska
- Tiếng Việt
- 中文