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}")