Beispiel

ggT(420,48) = ?

ggT(420,48) = 12

Algorithmus

Schritt 1

Dividiere die größere durch die kleinere Zahl und merke dir den Rest. Ist der Rest 0, so ist der Divior dieser Division der ggT.

Schritt 2

Der alte Divisor wird zum neuen Dividenden und der alte Rest zum neuen Divisor. Führe nun diese Division durch und merke dir den Rest. Ist der Rest 0, so ist der Divior dieser Division der ggT.

Schritt 3

Wiederhole Schritt 2 so lange, bis 0 Rest bleibt.

Programmablauf

Einlesen der Zahlen a und b.
Ist a < b? Wenn ja, dann tausche a mit b!
Wiederhole bis der Rest 0 ist:

Dividiere a durch b und merke dir den Rest: mod(a, b) ® Rest
a bekommt den Wert von b.
b bekommt den Wert vom Rest.

Ausgabe des ggT. (Ist der Rest = 0, dann enthält die Variable a den ggT(a,b).)

zurück