Python.Ввести с клавиатуры 2 натуральных числа и сравнить количество шагов цикла для вычисления их НОД с помощью обычного и модифицированного алгоритмов Евклида.Пример: Введите два числа: 1998 2 НОД(1998,2)=2 Обычный алгоритм: 998 Модифицированный: 1

Предыдущий
вопрос Следующий
вопрос

num1, num2 = map(int, input("Введите два числа: ").split())

def gcd(a, b):
while b:
a, b = b, a % b
return a

def modified_gcd(a, b):
if a == 0:
return b
if b == 0:
return a
if a == b:
return a
if a % 2 == 0 and b % 2 == 0:
return 2 * modified_gcd(a // 2, b // 2)
if a % 2 == 0 and b % 2 != 0:
return modified_gcd(a // 2, b)
if a % 2 != 0 and b % 2 == 0:
return modified_gcd(a, b // 2)
if a % 2 != 0 and b % 2 != 0 and a > b:
return modified_gcd((a - b) // 2, b)
if a % 2 != 0 and b % 2 != 0 and a < b:
return modified_gcd(a, (b - a) // 2)

gcd_result = gcd(num1, num2)
modified_gcd_result = modified_gcd(num1, num2)

print(f"НОД({num1}, {num2})={gcd_result}")
print(f"Обычный алгоритм: {gcd_result}")
print(f"Модифицированный: {modified_gcd_result}")