Алгоритм нахождения НОД по Евклиду:

Вводим два числа a и b, для которых необходимо найти НОД.Пока b не равно 0:
Находим остаток от деления a на b: r = a % b.Присваиваем a значение b: a = b.Присваиваем b значение r: b = r.Выводим значение a, которое и будет НОД.

Пример кода на Python:

def euclidean_gcd(a, b):
while b != 0:
r = a % b
a = b
b = r
return a
a = int(input("Введите первое число: "))
b = int(input("Введите второе число: "))
gcd = euclidean_gcd(a, b)
print("НОД чисел", a, "и", b, "равен", gcd)