Greatest Common Divisor

Q: Wie hoch ist die Zeitkomplexität des euklidischen Algorithmus?

Es läuft in O(log(min(a, b))) Schritten, da alle zwei Schritte mindestens die größere Zahl halbiert wird. Der ungünstigste Fall ist ein Paar aufeinanderfolgender Fibonacci-Zahlen. Für Zahlen bis zu 10^9 sind das höchstens 43 Schritte, und der Algorithmus verwendet O(1) zusätzlichen Speicherplatz.

Q: Warum ist gcd(a, b) gleich gcd(b, a % b)?

Schreibe a = q × b + r mit r = a % b . Eine Zahl, die a und b teilt, teilt a - q × b , also r . Eine Zahl, die b und r teilt, teilt q × b + r , also a . Beide Paare haben dieselben gemeinsamen Teiler und somit auch denselben größten gemeinsamen Teiler.

EinsteigerMathe und Simulation

+10

Du erhältst zwei positive ganze Zahlen a und b. Gib ihren größten gemeinsamen Teiler zurück: die größte ganze Zahl, die beide ohne Rest teilt.

Zum Beispiel sind die Zahlen, die sowohl 8 als auch 12 teilen, 1, 2 und 4, daher lautet die Antwort 4.

Funktion

gcd(a: integer, b: integer) → integer

ainteger: die erste positive ganze Zahl
binteger: die zweite positive ganze Zahl
Gibt zurückinteger: die größte ganze Zahl, die sowohl a als auch b teilt

Einschränkungen

1 ≤ a ≤ 10⁹
1 ≤ b ≤ 10⁹

Beispiele

Eingabe: a = 12b = 18
Ausgabe: 6
Erklärung: Die Teiler von 12 sind 1, 2, 3, 4, 6 und 12; die Teiler von 18 sind 1, 2, 3, 6, 9 und 18. Der größte Wert auf beiden Listen ist 6.

Eingabe: a = 17b = 5
Ausgabe: 1
Erklärung: 17 und 5 sind beide Primzahlen und verschieden, daher ist 1 der einzige Teiler, den sie gemeinsam haben.

Eingabe: a = 42b = 42
Ausgabe: 42
Erklärung: Eine Zahl teilt sich selbst, und nichts, das größer als 42 ist, kann 42 teilen. Daher ist der größte gemeinsame Teiler von 42 und 42 gleich 42.

+14 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du den Algorithmus von Euklid so erweitern, dass er auch ganze Zahlen x und y zurückgibt, für die a × x + b × y = gcd(a, b) gilt?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Die Definition legt nahe, die Kandidaten nacheinander auszuprobieren. Bei kleinen Zahlen funktioniert das. Bei a und b bis zu 10^9 wären bei zwei großen Zahlen ohne gemeinsamen Teiler jedoch eine Milliarde Versuche nötig. Euklids Beobachtung, dass gcd(a, b) gleich gcd(b, a % b) ist, verkleinert die Zahlen so schnell, dass kein Zahlenpaar bis zu 10^9 mehr als 43 Schritte benötigt.

Von der kleineren Zahl herunterzählen

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Ein gemeinsamer Teiler kann nicht größer als die kleinere der beiden Zahlen sein, denn ein Teiler von b ist höchstens b. Beginne also einen Kandidaten d bei min(a, b) und zähle ihn so lange um eins herunter, bis er beide Zahlen teilt. Da du die Kandidaten von oben her ausprobierst, ist der erste passende der größte.

Für 12 und 18 probierst du 12 (teilt 18 nicht), dann 11, 10, 9, 8 und 7, die alle nicht passen, und hältst bei 6 an. Die Schleife endet immer, weil 1 jede Zahl teilt.

Der Aufwand entspricht der Anzahl der Kandidaten. Für 999999937 und 999999929, zwei Primzahlen, lautet die Antwort 1, und die Schleife läuft fast 10^9 Mal. Das ist für die größten Tests viel zu langsam.

Algorithmus

Setze d auf den kleineren Wert von a und b.
Solange a % d oder b % d nicht 0 ist, ziehe 1 von d ab.
Gib d zurück.

def gcd(a, b):
    d = min(a, b)
    while a % d != 0 or b % d != 0:
        d -= 1
    return d

Euklidischer Algorithmus

Idee

Schreibe a = q × b + r, wobei r = a % b gilt. Jede Zahl, die sowohl a als auch b teilt, teilt auch r = a - q × b. Jede Zahl, die sowohl b als auch r teilt, teilt auch a = q × b + r. Die Paare (a, b) und (b, r) haben also genau dieselben gemeinsamen Teiler und denselben größten gemeinsamen Teiler.

Ersetze (a, b) durch (b, a % b) und wiederhole den Vorgang, bis b gleich 0 ist. Jede Zahl teilt 0, also gilt gcd(a, 0) = a und a ist das Ergebnis. Für 12 und 18: Aus (12, 18) wird (18, 12), dann (12, 6), dann (6, 0), und das Ergebnis ist 6. Im ersten Schritt werden die Zahlen automatisch vertauscht, wenn a kleiner ist. Du musst sie also nie sortieren.

Alle zwei Schritte halbiert sich die größere Zahl mindestens, daher wird die Schleife O(log(min(a, b))) Mal durchlaufen. Die langsamsten Eingaben sind aufeinanderfolgende Fibonacci-Zahlen wie 701408733 und 433494437, und selbst für sie sind nur 42 Schritte nötig.

Algorithmus

Solange b nicht 0 ist, berechne r = a % b.
Setze a = b und b = r.
Wenn b 0 erreicht, gib a zurück.

def gcd(a, b):
    # gcd(a, b) == gcd(b, a % b), and gcd(a, 0) == a.
    while b != 0:
        a, b = b, a % b
    return a

Stolperfallen und Grenzfälle

Der Algorithmus ist kurz, daher entstehen die Fehler durch die Aktualisierung und die Abbruchbedingung.

Aktualisierung in der falschen Reihenfolge. a = b gefolgt von b = a % b berechnet b % b, was immer 0 ergibt, und gibt b zurück. Speichere den Rest zuerst in einer temporären Variable oder weise beide Werte gleichzeitig zu.
Am Ende der Schleife b statt a zurückgeben. Zu diesem Zeitpunkt ist b 0.
Den Countdown bei 2 beenden oder ihn bei max(a, b) beginnen. Ersteres übersieht teilerfremde Paare wie 17 und 5; Letzteres verschwendet Zeit mit Kandidaten, die die kleinere Zahl nicht teilen können.
Wiederholte Subtraktion statt des Rests verwenden. gcd(10^9, 1) benötigt dann eine Milliarde Subtraktionen; % erledigt sie alle in einem Schritt.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität des euklidischen Algorithmus?

Es läuft in O(log(min(a, b))) Schritten, da alle zwei Schritte mindestens die größere Zahl halbiert wird. Der ungünstigste Fall ist ein Paar aufeinanderfolgender Fibonacci-Zahlen. Für Zahlen bis zu 10^9 sind das höchstens 43 Schritte, und der Algorithmus verwendet O(1) zusätzlichen Speicherplatz.

Warum ist gcd(a, b) gleich gcd(b, a % b)?

Schreibe a = q × b + r mit r = a % b. Eine Zahl, die a und b teilt, teilt a - q × b, also r. Eine Zahl, die b und r teilt, teilt q × b + r, also a. Beide Paare haben dieselben gemeinsamen Teiler und somit auch denselben größten gemeinsamen Teiler.

Was ist der Unterschied zwischen dem größten gemeinsamen Teiler (GGT) und dem kleinsten gemeinsamen Vielfachen (KGV)?

Der größte gemeinsame Teiler ist die größte Zahl, die beide Eingaben teilt; das kleinste gemeinsame Vielfache ist die kleinste Zahl, durch die beide Eingaben teilbar sind. Sie sind durch gcd(a, b) × lcm(a, b) = a × b miteinander verknüpft. Sobald du also den größten gemeinsamen Teiler hast, ist das kleinste gemeinsame Vielfache a / gcd(a, b) × b.

Was ist der größte gemeinsame Teiler zweier teilerfremder Zahlen?

Zwei Zahlen sind teilerfremd, wenn ihr größter gemeinsamer Teiler 1 ist, das heißt, sie haben keinen gemeinsamen Primfaktor. Zwei verschiedene Primzahlen sind immer teilerfremd, ebenso wie zwei aufeinanderfolgende ganze Zahlen, zum Beispiel 8 und 9.

Python

def gcd(a, b):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

a = 12
b = 18

Erwartet