Решение модуля 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 = a % b
    else:
        b = b % a
 
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))