Алгоритм Евклида - нахождение наибольшего общего делителя

Алгоритм Евклида – это алгоритм нахождения наибольшего общего делителя (НОД) пары целых чисел.

Наибольший общий делитель (НОД) – это число, которое делит без остатка два числа и делится само без остатка на любой другой делитель данных двух чисел. Проще говоря, это самое большое число, на которое можно без остатка разделить два числа, для которых ищется НОД.

Алгоритм нахождения НОД делением

  1. Большее число делим на меньшее.
  2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).
  3. Если есть остаток, то большее число заменяем на остаток от деления.
  4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 / 18 = 1 (остаток 12)
18 / 12 = 1 (остаток 6)
12 / 6 = 2 (остаток 0) 
Конец: НОД – это делитель 6.
НОД (30, 18) = 6

a = 50
b = 130
 
while a != 0 and b != 0:
    if a > b:
        a = a % b
    else:
        b = b % a
 
print(a + b)

В цикле в переменную a или b записывается остаток от деления. Цикл завершается, когда хотя бы одна из переменных равна нулю. Это значит, что другая содержит НОД. Однако какая именно, мы не знаем. Поэтому для НОД находим сумму этих переменных. Поскольку в одной из переменных ноль, он не оказывает влияние на результат.

Алгоритм нахождения НОД вычитанием

  1. Из большего числа вычитаем меньшее.
  2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла).
  3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания.
  4. Переходим к пункту 1.

Пример:
Найти НОД для 30 и 18.
30 - 18 = 12
18 - 12 = 6
12 - 6 = 6
6 - 6 = 0
Конец: НОД – это уменьшаемое или вычитаемое.
НОД (30, 18) = 6

a = 50
b = 130
 
while a != b:
    if a > b:
        a = a - b
    else:
        b = b - a
 
print(a)

Функция вычисления НОД

def gcd(a, b):
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a        
    print(a)

Блок-схема алгоритма Евклида

Блок-схема алгоритма Евклида

Комментарии

Стоило бы отметить, что время выполнения первого алгоритма (основаного на остатках от деления) намного меньше, чем второго (вычитанием), то есть он эффективнее

Ответ на от Сергей

решая задачу, чем заменить классику по эуклиду, само собой пришло в голову вычитание, как простая операция, хорошо вписывающаяся в конвейер. но при огромном делимом и малом делителе - алгоритм работает вечность, против классических перестановок

В коде нахождения НОД делением в цикле while должно стоять условие a!=0 or b!=0, вместо a!=0 and b!=0