LU04.A05: Grösster gemeinsamer Teiler

Bei mathematischen Programmen wird häufig der grösste gemeinsame Teiler (ggT) von zwei natürlichen Zahlen benötigt. Aus dem Mathematik-Unterricht kennen sie vermutlich die Methode mit der Primfaktorzerlegung.

Diese Zerlegung ist sehr schwierig zu programmieren. Wesentlich einfacher ist ein Algorithmus der ursprünglich von Euklid entwickelt wurde:

1. Der Benutzer gibt die beiden Zahlen number1 und number2 ein.
2. Solange die number2 ≠ 0 ist,
   1. berechnet das Programm den ganzzahligen rest aus number1 / number2,
   2. nun wird der Wert von number2 wird in number1 gespeichert,
   3. und der Wert von rest in number2 gespeichert.
3. Gib den Wert der Variable number1 aus.

© Marcel Suter