Модуль 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))