НОД — нахождение наибольшего общего делителя для 2 чисел

от

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

НОД — для не отрицательных чисел a и b, которые > 0 — это не отрицательное, целое число которое делит и а и b.

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

Если а = 0, вернуть b

Если b = 0, вернуть a

Далее, необходимо поделить большее из 2-ух чисел на меньшее и присвоить получившийся остаток от деления большему числу.

Пример:

  1. НОД(3918848, 1653264) = 3918848 % 1653264 = 612320
  2. НОД(612320, 1653264) = 1653264 % 612320 = 428624
  3. НОД(612320, 428624) = 612320 % 428624 =  183964
  4. НОД(183964, 428624) = 428624 % 183964 = 61232
  5. НОД(183964, 61232) = 183964 % 61232 = 0
  6. НОД(0, 61232) => 61232
def gcd(a, b):
    if a == 0:
        return b
    if b == 0:
        return a
    if a >= b:
        return gcd(a%b, b)
    if b >= a:
        return gcd(a, b%a)

a = 18
b = 35
print(gcd(a, b))
# >>> 1

Еще одна версия, с не меньшей производительностью, но без явного ветвления (if):

def gcd2(a, b):
    if a == 0 or b == 0:
        return max(a, b)
    return gcd2(b%a, a)