#Найти наибольший общий делитель двух целых чисел,
#используя алгоритм Евклида
#при помощи рекурсии

def nod_rec(num1, num2):
 if num1==0 :
  return num2
 if num2==0 :
  return num1
 if num2>num1 :
  return nod_rec(num1,num2-num1)
 else:
  return nod_rec(num1-num2,num2)

print ('Введите два натуральных числа')
a = int( input("1 число: "))
b = int( input("2 число: "))
print ('НОД = ', nod_rec(a,b) )