#!/usr/bin/env python3

"""

Dieses Programm implementiert den euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers zweier Zahlen rekursiv.

(In Level 3 findet sich eine iterative Implementation.)

"""

# Berechnung

def ggT(a: int, b: int) -> int:

# Beide Zahlen sollten positiv sein.

# Wir nehmen einfach den Betrag.

a = abs(a)

b = abs(b)

# a soll größer sein als b.

# Falls das nicht bereits der Fall ist,

# tauschen wir die beiden einfach.

if b > a:

return ggT(b, a)

# Wenn b Null ist, sind wir fertig und a ist der ggT.

# Ansonsten müssen wir (nochmal) rechnen.

if b == 0:

return a

# Teile a mit Rest durch b;

# setze a auf b

# und b auf den Rest.

return ggT(b, a%b)

# Eingabe

a = int(input("erste Zahl eingeben: "))

b = int(input("zweite Zahl eingeben: "))

# Ausgabe

print("Der größte gemeinsame Teiler dieser Zahlen ist:", ggT(a, b))