Python-Algorithmen

Den größten gemeinsamen Teiler mit dem euklidischen Algorithmus in Python finden

In dieser Lektion findest du den größten gemeinsamen Teiler (ggT) zweier Zahlen mit dem euklidischen Algorithmus.

  • Fortgeschritten
  • 2 Min. Lesezeit
  • 1 ausführbares Beispiel

Einführung

Das Problem

Beim Kürzen von Brüchen, beim Aufteilen in gleich große Gruppen und in vielen Rätseln brauchst du die größte Zahl, durch die sich zwei Zahlen ohne Rest teilen lassen. Jeden Kandidaten auszuprobieren ist bei großen Zahlen langsam. Euklid hat vor über 2.000 Jahren einen viel schnelleren Weg gefunden.

Stell es dir so vor

Euklids Verfahren ist, als würdest du ein Rechteck mit möglichst großen quadratischen Fliesen auslegen. Schneide aus einem Rechteck von 48 × 18 das größtmögliche Quadrat aus, dann aus dem Rest, und so weiter. Geht es irgendwann genau auf, ohne dass etwas übrig bleibt, ist die Seitenlänge des letzten Quadrats die Antwort.

Vom Quadrateschneiden zum Code
first, second▭ Das Rechteck: 48 × 18
first % second✂️ Was übrig bleibt, wenn du Quadrate mit der kürzeren Seite ausschneidest
first, second = second, first % second🔁 Mit dem Reststück wiederholen
while second:✅ Kein Rest mehr: die Seite ist der ggT, 6
gcd(a, b) = gcd(b, a % b), bis der Rest 0 ist.
In einem Satz

Der größte gemeinsame Teiler (ggT, englisch GCD) zweier ganzer Zahlen ist die größte positive ganze Zahl, die beide teilt. Der euklidische Algorithmus findet ihn, indem er das Paar (a, b) durch (b, a % b) ersetzt, bis b gleich 0 ist.

Das Wichtigste

  1. first, second = second, first % second ersetzt das Paar durch die kleinere Zahl und den Rest.
  2. Für 48 und 18 sind die Paare (48, 18), (18, 12), (12, 6), (6, 0).
  3. while second: endet, wenn der Rest 0 wird.
  4. return abs(first) liefert auch bei negativen Eingaben ein positives Ergebnis.

Wann verwendet man das?

  • Brüche und Verhältnisse kürzen.
  • Das kleinste gemeinsame Vielfache finden: a * b // gcd(a, b).
  • Zahlenrätsel, modulare Arithmetik und Grundlagen der Kryptografie.

Wann du es nicht brauchst

  • Echter Code: math.gcd ist eingebaut und nimmt in neueren Python-Versionen beliebig viele Argumente.
  • Alle gemeinsamen Teiler finden: Der ggT liefert nur den größten.

Beispielcode

Code ausführen →
main.py
def gcd(first, second):
    while second:
        first, second = second, first % second
    return abs(first)

print(gcd(48, 18))
Run-Button für dieses Beispiel erstellen

Ergebnis der Ausführung

6

Erklärung des Codes

In jedem Schritt wird das Paar (first, second) durch (second, first % second) ersetzt. Ist der Rest 0, ist der in first verbliebene Wert der ggT, der ggT von 48 und 18 ist also 6. Die Funktion abs() sorgt dafür, dass das Ergebnis immer positiv ist. Die Zahl der Schritte wächst mit der Größe der Zahlen nur sehr langsam, etwa O(log n).

Ändere die Werte und führe das Programm im CodeUtility Python Online-Compiler aus, ohne Python lokal zu installieren.

Übungen zur Vertiefung

Ändere den Code anhand der folgenden Vorschläge. Wenn du selbst etwas änderst und das Ergebnis beobachtest, verstehst du viel mehr, als wenn du den Code nur liest.

  1. Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
  2. Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
  3. Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Im Python-Compiler ausführen →

Häufige Fehler

Subtraktion statt Rest verwenden

Wiederholtes Subtrahieren liefert dieselbe Antwort, ist aber bei weit auseinanderliegenden Zahlen sehr langsam.

Problem
while first != second:
    if first > second:
        first -= second
    else:
        second -= first
Lösung
while second:
    first, second = second, first % second

Lektion fertig?

Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.

Mit einer Challenge üben

Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.

Alle Challenges