Найти наибольший общий делитель (НОД). Алгоритм Евклида

# Наибольший общий делитель
# двух натуральных чисел - это
# самое большое натуральное число,
# которое нацело делит исходные два числа.
# Алгоритм Евклида - это способ
# нахождения НОД с помощью
# последовательного деления или вычитания.

# Исходные числа, для которых ищется НОД.
a = int(input())
b = int(input())

# Пока оба числа не равны нулю,
while a != 0 and b != 0:
    # будем сравнивать их между собой.

    # Если первое число больше второго,
    if a > b:
        # то найдем остаток от деления
        # его на второе число и присваивать
        # остаток первой переменной.
        a = a % b

    # Иначе (когда второе число больше первого)
    else:
        # присваивать второй переменной
        # остаток от деления нацело
        # второго числа на первое
        b = b % a

# Теперь одно из чисел содержит 0,
# а другое - НОД, но какое - неизвестно.
# Проще сложить числа,
# чем писать конструкцию if-else.
gcd = a + b
print(gcd)
128
48
16


Вы можете оставить комментарий, или Трекбэк с вашего сайта.

Оставить комментарий