LU04.A05: Grösster gemeinsamer Teiler

Lösen Sie die Aufgabe mit BlockPy oder Codingrooms

Laden Sie einen Screenshot ihres Blockly-Ablaufs hoch.

Aufgabe

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.

Die mathematische Funktion Modulo berechnet den ganzzahligen Rest einer Division. Zum Beispiel:

342 geteilt in 5 ergibt 68 und den Rest 2, also 342 Modulo 5 = 2.

,

© Marcel Suter