Могу такое предложить. Выглядит пугающе, но зато придумал сам. И ни каких тебе Евклидов. Плюс ищет НОД не только для двух, а для любого количества чисел (ну конечно если их не астрономическое количество, тогда будет работать медленно)
Вот def nod(a,b):
while a%b!=0:
a,b = b,a%b
return b
print(nod(int(input("a = ")),int(input("b = "))))
Вы точно не прочитали вторую страницу первого тома Искусства программирования нашего Дональда Эрвина Кнута ?