Question

Напишите программу Пожалуйста

Алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел, формулируется так: нужно заменять большее число на разность большего и меньшего до тех пор, пока одно из них не станет равно нулю; тогда второе и есть НОД. Напишите программу, которая реализует этот алгоритм.


Входные данные

Входная строка содержит два числа, разделённые пробелом – a и b .


Выходные данные

Программа должна вывести в одной строке два числа: сначала наибольший общий делитель двух введённых чисел, а затем – количество шагов цикла, которые были выполнены.


Примеры

входные данные

14 21

выходные данные

7 3

входные данные

171 3534

выходные данные

57 23

Язык Pyton Tutor

Answer 1

def gcd(a, b):

   y = 0

   while a != b:

       y += 1

       if a > b:

           a = a - b

       else:

           b = b - a        

   print("%s%s" % (a, y))

string = str(input())

args = string.split(' ')

a, b = int(args[0]), int(args[1])

gcd(a, b)