GCD (größter gemeinsamer Teiler) – Euklids Algorithmus
Nachdem wir den Algorithmus mehrmals ausgeführt haben, fällt auf, dass einige Operationen überflüssig sind und die Berechnung des GCD (ggT) tatsächlich optimiert werden kann.
Bei der Methode mit Subtraktionen ziehen wir immer wieder die kleinere Zahl von der größeren ab, bis wir 0 oder die gesuchte Zahl (den ggT) erhalten. Dies können wir beschleunigen, indem wir statt der wiederholten Subtraktion den Rest der Division der größeren durch die kleinere Zahl finden. Mit der Modulo-Operation teilen wir die größere Zahl mehrfach durch die kleinere und betrachten fortlaufend den Rest, bis dieser 0 wird. Der letzte Rest ungleich 0 ist dabei der ggT.
Man kann sich die Modulo-Operation als eine effizientere Variante zur Bestimmung des ggT vorstellen. Anstatt die kleinere Zahl mehrfach von der größeren abzuziehen, nutzen wir die Division, um die größere Zahl schneller zu reduzieren. Dabei teilen wir die beiden Zahlen durch ihre gemeinsamen Teiler und nähern uns dem ggT somit deutlich schneller an.
a, b = int(input()), int(input())
while a > 0 and b > 0: # Falls a oder b = 0 => dann ist der andere der ggT
a, b = b, a % b # gcd von (a, b) ist gleich gcd von (b, a % b)
d = b if a == 0 else a # wenn a = 0 => b ist der ggT, wenn b = 0 => a ist der ggT
print('gcd:', d)Dieser Algorithmus wurde erstmals in Euklids Werk um 300 v. Chr. erwähnt.
Lassen Sie uns den Algorithmus in einigen Beispielen durchspielen:
a = 8, b = 12
- a = 12, b = 8
- a = 8, b = 4
- a = 4, b = 0
- break ⇒ GCD = 4
a = 54, b = 24
- a = 24, b = 6
- a = 6, b = 0
- break ⇒ GCD = 6
a = 17, b = 16
- a = 16, b = 1
- a = 1, b = 0
- break ⇒ GCD = 1
Eingabe
Die einzige Zeile der Eingabe enthält zwei ganze Zahlen
a und b (0 ≤ a, b ≤ ).Ausgabe
Das Programm soll den größten gemeinsamen Teiler von
a und b ausgeben.Examples
Input | Output |
8 12 | 4 |
54 24 | 6 |
17 16 | 1 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB