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.
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.
first, second▭ Das Rechteck: 48 × 18first % second✂️ Was übrig bleibt, wenn du Quadrate mit der kürzeren Seite ausschneidestfirst, second = second, first % second🔁 Mit dem Reststück wiederholenwhile second:✅ Kein Rest mehr: die Seite ist der ggT, 6Der 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
first, second = second, first % secondersetzt das Paar durch die kleinere Zahl und den Rest.- Für 48 und 18 sind die Paare (48, 18), (18, 12), (12, 6), (6, 0).
while second:endet, wenn der Rest 0 wird.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.gcdist eingebaut und nimmt in neueren Python-Versionen beliebig viele Argumente. - Alle gemeinsamen Teiler finden: Der ggT liefert nur den größten.
Beispielcode
def gcd(first, second):
while second:
first, second = second, first % second
return abs(first)
print(gcd(48, 18))
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.
- Teste mit einer leeren Liste, einer Liste mit nur einem Element und einer Liste mit doppelten Werten.
- Gib den Zustand nach jedem Schritt aus, um den Algorithmus bei der Arbeit zu beobachten.
- Miss die Laufzeit mit 100, 1.000 und 10.000 Elementen und vergleiche sie mit einer anderen Lösung.
Häufige Fehler
Subtraktion statt Rest verwenden
Wiederholtes Subtrahieren liefert dieselbe Antwort, ist aber bei weit auseinanderliegenden Zahlen sehr langsam.
while first != second:
if first > second:
first -= second
else:
second -= first
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.
- Größter gemeinsamer Teiler Finde die größte Zahl, die beide Werte teilt. Einfach
- Kleinstes gemeinsames Vielfaches Finde die kleinste positive Zahl, die durch beide Werte teilbar ist. Einfach
- Exakte Bruchrechnung Führe Bruchoperationen durch und gib einen gekürzten Bruch zurück. Mittel