Алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел, формулируется так... Python!!!!

Question

Алгоритм Евклида для вычисления наибольшего общего делителя двух натуральных чисел, формулируется так... Python!!!!

juli Ученик (211), закрыт 9 месяцев назад

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

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

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

Примеры
входные данные
14 21
выходные данные
7 3
_______________________
входные данные
171 3534
выходные данные
57 23

Answer 1

Вообще-то в Python уже есть встроенная реализация:

 import math
print(math.gcd(*map(int, input().split())))

Но если надо вручную, то:

 def gcd(a, b): return gcd(b, a % b) if b else a
print(gcd(*map(int, input().split())))

И, да - это именно алгоритм Евклида: нормальная реализация через нормальный остаток от деления, а не через кучу бессмысленную вычитаний ради получения этого остатка.

С кол-вом гипотетических итераций:

 def gcd(a, b, c = 0): return gcd(b, a % b, c + a // b) if b else [a, c] 
print(*gcd(*map(int, input().split())))