Euklidischer Algorithmus
Der Euklidische Algorithmus ist ein klassisches mathematisches Verfahren zur Berechnung des größten gemeinsamen Teilers (ggT) zweier natürlicher Zahlen. Er basiert auf der Erkenntnis, dass der ggT zweier Zahlen gleich dem ggT der kleineren Zahl und dem Rest der Division ist. Der Algorithmus wird so lange wiederholt, bis der Rest 0 ist – der letzte Divisor ist dann der ggT. In der Informatik ist er ein grundlegendes Beispiel für rekursive und iterative Algorithmen.