Uitwerking: gcd implementeren
a = 1081
b = 483
# Simpele uitwerking: begin bij het kleinste getal van a en b en probeer.
# Het eerste getal dat zowel a als b deelt is dan de grootste gemene deler.
for d in range(min(a, b), 0, -1):
if a % d == 0 and b % d == 0:
break
print("De grootste gemene deler van", a, "en", b, "is", d)
# Geavanceerde uitwerking gebaseerd op het Euclidisch algoritme.
# Korte uitleg: Dit werkt vanaf twee observaties:
# 1. als d een deler is van a en b, dan is het ook een deler van a-b.
# 2. gcd(a, 0) = a want elk getal deelt 0.
# Stel dat a > b, dan kunnen we zo vaak mogelijk b van a aftrekken zonder
# de gcd te veranderen: gcd(a, b) = gcd(a-b, b) = gcd(a - 2b, b) = ...
# net zo lang tot a-nb < b, in andere woorden: gcd(a, b) = gcd(a % b, b)
# Merk op dat a % b < b, dus we draaien ze om. Dit herhalen we tot b = 0.
print(f"De grootste gemene deler van {a} en {b} is ", end="")
while b != 0:
a, b = b, a % b
print(a)
