GGT, KGV und der euklidische Algorithmus
Berechnen Sie Teiler schnell und korrekt
GGT, KGV und der euklidische Algorithmus ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Warum Teiler wichtig sind
Viele Wettbewerbsaufgaben hängen von gemeinsamen Faktoren zweier Zahlen ab. Das wichtigste Werkzeug dafür ist der GCD, der größte gemeinsame Teiler. 🔢
Was GCD bedeutet
Der GCD zweier Ganzzahlen ist die größte Zahl, durch die sich beide ohne Rest teilen lassen. Für 12 und 18 ist er 6, da 6 beide Zahlen ohne Rest teilt.
Der langsame Weg
Sie könnten ausgehend vom kleineren Wert jede Zahl abwärts prüfen, bis eine beide Zahlen teilt. Das funktioniert, ist für große Eingaben aber viel zu langsam.
Die Erkenntnis des Euklidischen Algorithmus
Der Euklidische Algorithmus ist der schnelle Weg. Seine zentrale Idee lautet: Der GCD von a und b ist gleich dem GCD von b und dem Rest der Division von a durch b.
Die Rekurrenz
Wiederholen Sie den Schritt aus Vertauschen und Modulo-Operation, bis der Rest null ist. Der letzte verbleibende Wert ungleich null ist Ihre Antwort, also der GCD selbst.
gcd(a, b) = gcd(b, a % b)
gcd(a, 0) = aImplementieren Sie es selbst
Eine kurze Schleife ersetzt das Zahlenpaar immer wieder, bis b null erreicht. Das Verfahren benötigt ungefähr log Schritte und ist selbst für riesige Zahlen blitzschnell.
def gcd(a, b):
while b:
a, b = b, a % b
return aVerwenden Sie die Standardbibliothek
Sie müssen den Algorithmus nur selten selbst implementieren. Python liefert math.gcd mit, das korrekt und schnell ist und Argumente mit dem Wert null für Sie verarbeitet.
from math import gcd
print(gcd(12, 18))Vom GCD zum LCM
Das LCM, das kleinste gemeinsame Vielfache, ist die kleinste Zahl, durch die sich beide Werte teilen lassen. Es steht in direktem Zusammenhang mit dem soeben berechneten GCD.
Die LCM-Formel
Multiplizieren Sie die beiden Zahlen und teilen Sie anschließend durch ihren GCD. Teilen Sie immer zuerst, um bei sehr großen Produkten einen Überlauf zu vermeiden.
def lcm(a, b):
return a // gcd(a, b) * bGCD einer vollständigen Liste
Um den GCD über viele Zahlen zu berechnen, wenden Sie ihn paarweise nacheinander an. Pythons reduce wendet math.gcd von links nach rechts auf die Liste an.
from functools import reduce
from math import gcd
g = reduce(gcd, nums)Den Fall null behandeln
Per Definition gilt gcd(a, 0) = a und gcd(0, 0) = 0. Wenn Sie diesen Sonderfall kennen, verhalten sich Ihre Schleifen auch bei leerer Eingabe korrekt.
Schnelltest
Zeit, den zentralen Schritt des Euklidischen Algorithmus zu überprüfen.
Zusammenfassung
Sie können jetzt den GCD mit dem Euklidischen Algorithmus in logarithmischer Zeit berechnen, daraus das LCM ableiten und beide Werte über eine Liste hinweg berechnen. ✅
Häufig gestellte Fragen
Ist die Lektion „GGT, KGV und der euklidische Algorithmus“ kostenlos?
Ja — der vollständige Text von „GGT, KGV und der euklidische Algorithmus“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „GGT, KGV und der euklidische Algorithmus“?
Berechnen Sie Teiler schnell und korrekt Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „GGT, KGV und der euklidische Algorithmus“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- GGT, KGV und der euklidische Algorithmus
- Primzahltest bis sqrt(n)
- Sieb des Eratosthenes
- Primfaktorzerlegung und Teiler