Решение модуля 4.5 Инди-курс программирования на Python

Модуль 4.5 (Алгоритм Евклида). Алгоритм Евклида позволяет найти наибольший общий делитель (НОД) для двух чисел.

Ниже представлены примеры задач с решением на тему Алгоритм Евклида.

Как расшифровывается аббревиатура НОД?

Наибольший общий делитель

Чему равен НОД чисел 23 и 17

1

Посчитайте при помощи метода, рассказанного в видео, значение НОДа чисел 345 и 555

15

Даны два натуральных числа A и B. Требуется найти их наибольший общий делитель (НОД) методом вычитания

# загружаем данные 
a,b=map(int,input().split()) 

while a!=b:        # пока переменные не равны 
    if a>b:        # вычитаем 
        a-=b       # из большего    
    else:          # меньшее 
        b-=a       # результат НОД

print(a)           

Та же самая задача, необходимо найти НОД двух чисел, только теперь нужно модернизировать свой код при помощи нахождения остатка от деления

a, b = map(int, input().split())

# Пока оба числа не равны нулю
while a != 0 and b != 0:
    if a > b:
        # Если a больше b, вычисляем остаток от деления a на b
        a = a % b
    else:
        # Иначе, если b больше a, вычисляем остаток от деления b на a
        b = b % a

# После выхода из цикла a или b будет равно нулю, а другое число будет НОД.
# Выводим сумму a и b, которая и будет значением НОД.
print(a + b)

Как расшифровывается аббревиатура НОК?

Наименьшее общее кратное

Чему равен НОК чисел 35 и 5?

35

Чему равен НОК чисел 75 и 120?

600

Даны два натуральных числа A и B. Требуется найти их наименьшее общее кратное (НОК).

# НОК = (A * B) / НОД       # A и B в первоначальном виде.

a, b = map(int, input().split())
# Создоем переменную для НОК (наименшее общее кратное)
z = a * b

# Нахоdим НОД (наибольший общий делитель)
while b > 0:
    a, b = b, a % b
    
#Находим НОК
print(int(z / a))