Algorithmen und Datenstrukturen

Größter gemeinsamer Teiler (GGT) mit Subtraktion

Gegeben sind zwei positive ganze Zahlen a und b, deren größter gemeinsamer Teiler berechnet werden soll. Da diese Zahlen jedoch sehr groß sein können, ist es nicht effizient, alle Teiler von a und b zu bestimmen und den größten gemeinsamen zu suchen. Stattdessen müssen wir den Algorithmus optimieren.
Nehmen wir an, dass a > b. Wenn wir von einem gemeinsamen Teiler d ausgehen, so sind sowohl a als auch b durch d teilbar. Das bedeutet:
wobei x und y ganze Zahlen sind. Wenn wir b von a subtrahieren, erhalten wir:
 
Somit ist d ein Teiler von sowohl a als auch b, und da x und y ganze Zahlen sind, ist auch x-y eine ganze Zahl. Folglich muss d ebenfalls ein Teiler von a-b sein. Diese Beobachtung hilft uns, die Anzahl der Schritte zur Bestimmung des GGT zu minimieren.
Wenn der größte gemeinsame Teiler d sowohl a als auch b und zusätzlich a-b teilt, können wir d finden, indem wir statt mit a (das größere sein kann) jetzt mit b und a-b weitermachen. Dieser Vorgang wird wiederholt, bis entweder a oder b 0 wird (in diesem Fall ist die nicht-null Zahl der größte gemeinsame Teiler):
a, b = int(input()), int(input())
while a > 0 and b > 0:  # Falls a oder b 0 ist => die andere Zahl ist der GGT
    if b > a:           # Wir halten a immer >= b
        a, b = b, a     # Zahlen tauschen
    a, b = a - b, b     # gcd(a, b) entspricht gcd(a, b - a)

d = b if a == 0 else a  # Wenn a 0 ist => b ist der GGT, wenn b 0 ist => a ist der GGT
print('gcd:', d)
Nachfolgend einige Beispielabläufe des Algorithmus:
a = 8, b = 12
  1. b > a ⇒ tauschen ⇒ a = 12, b = 8
  1. b > a ⇒ tauschen ⇒ a = 8, b = 4
  1. a = 4 - 4 = 0, b = 4
  1. Abbruch ⇒ GGT = 4
a = 54, b = 24
  1. a = 54 - 24 = 30, b = 24
  1. a = 30 - 24 = 6, b = 24
  1. b > a ⇒ tauschen ⇒ a = 24, b = 6
  1. a = 18 - 6 = 12, b = 6
  1. a = 12 - 6 = 6, b = 6
  1. a = 6 - 6 = 0, b = 6
  1. Abbruch ⇒ GGT = 6
a = 17, b = 16
  1. a = 17 - 16 = 1, b = 16
  1. b > a ⇒ tauschen ⇒ a = 16, b = 1
  1. a = 14, b = 1
  1. a = 13, b = 1
  1. a = 12, b = 1
  1. …
  1. …
  1. a = 0, b = 1
  1. Abbruch ⇒ GGT = 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.

Beispiele

Input
Output
8 12
4
54 24
6
17 16
1

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue