Напишите функцию gcd(a, b) для вычисления наибольшего общего делителя двух натуральных чисел по алгоритму Евклида (через остаток от деления).
while b: a,b = b,a%b
Алгоритм Евклида основан на том, что $\gcd(a, b) = \gcd(b, a \bmod b)$, и базе $\gcd(a, 0) = a$.
Итеративно:
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return a
print(gcd(48, 36)) # 12
print(gcd(100, 75)) # 25
print(gcd(17, 13)) # 1 — взаимно простые
Рекурсивно:
def gcd(a: int, b: int) -> int:
return a if b == 0 else gcd(b, a % b)
Разбор для $\gcd(48, 36)$:
Сложность алгоритма Евклида: $O(\log \min(a,b))$.
В стандартной библиотеке есть math.gcd:
from math import gcd
print(gcd(48, 36)) # 12
Через НОД легко найти НОК: $\text{lcm}(a,b) = a \cdot b / \gcd(a,b)$.
Razbery — про разбор, не про списывание. Объяснение обязательно.