Least Common Multiple

Q: Wie lautet die Formel für das kgV zweier Zahlen?

lcm(a, b) = a × b / gcd(a, b) , berechnet als a / gcd(a, b) × b , damit kein Zwischenwert das Ergebnis überschreitet. Für 4 und 6 ist der gcd 2 , und 4 / 2 × 6 = 12 .

Q: Wie hoch ist die Zeitkomplexität der Berechnung des kgV?

Mit der ggT-Formel beträgt die Laufzeit O(log(min(a, b))) , also die Kosten des euklidischen Algorithmus, und der Speicherbedarf O(1) . Das Durchlaufen der Vielfachen der größeren Zahl hat eine Laufzeit von O(min(a, b)) , und das Zählen in Einerschritten hat eine Laufzeit von O(lcm(a, b)) .

Q: Wie findet man das kgV von mehr als zwei Zahlen?

Falte die Liste: lcm(a, b, c) = lcm(lcm(a, b), c) . Für [4, 6, 10] gilt: lcm(4, 6) = 12 und lcm(12, 10) = 60 . Der laufende Wert wächst schnell, verwende daher 64-Bit-Ganzzahlen, wenn die Liste lang ist.

EinsteigerMathe und Simulation

+10

Du erhältst zwei positive ganze Zahlen a und b. Gib ihr kleinstes gemeinsames Vielfaches zurück: die kleinste positive ganze Zahl, durch die sowohl a als auch b ohne Rest teilbar sind.

Funktion

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

ainteger: die erste positive ganze Zahl
binteger: die zweite positive ganze Zahl
Gibt zurückinteger: die kleinste positive ganze Zahl, die ein Vielfaches sowohl von a als auch von b ist

Einschränkungen

1 ≤ a ≤ 10⁶
1 ≤ b ≤ 10⁶
Die Antwort passt in eine vorzeichenbehaftete 32-Bit-Ganzzahl: lcm(a, b) ≤ 2³¹-1. Das Produkt a × b möglicherweise nicht.

Beispiele

Eingabe: a = 4b = 6
Ausgabe: 12
Erklärung: Die Vielfachen von 6 beginnen mit 6, 12, 18; die Vielfachen von 4 beginnen mit 4, 8, 12. Die erste Zahl auf beiden Listen ist 12.

Eingabe: a = 7b = 3
Ausgabe: 21
Erklärung: 7 und 3 haben keinen gemeinsamen Faktor außer 1, daher ist ihr kleinstes gemeinsames Vielfaches ihr Produkt, 21.

Eingabe: a = 15b = 45
Ausgabe: 45
Erklärung: 15 teilt 45 ohne Rest, also ist 45 bereits ein Vielfaches von beiden, und es gibt kein kleineres Vielfaches von 45.

Weiterführende Frage

Kannst du den größten gemeinsamen Teiler ganz ohne Division oder Rest berechnen, nur durch Subtraktion und Halbieren?

Tipps

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

0 von 3 geöffnet

Lösung

Das kleinste gemeinsame Vielfache und der größte gemeinsame Teiler hängen durch eine Tatsache zusammen: gcd(a, b) × lcm(a, b) = a × b. Die schnelle Antwort lautet also a × b / gcd(a, b). Das Produkt kann 10^12 erreichen und einen 32-Bit-Integer überlaufen lassen, selbst wenn das Ergebnis hineinpasst. Teile deshalb zuerst durch den ggT, bevor du multiplizierst.

Von der größeren Zahl aus hochzählen

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

Idee

Die Antwort ist mindestens so groß wie die größere Zahl. Setze m auf max(a, b) und addiere 1, bis beide Zahlen die Zahl teilen; du probierst die Kandidaten in aufsteigender Reihenfolge, daher ist der erste Treffer das kleinste gemeinsame Vielfache. Bei 4 und 6 probierst du 6 bis 11 und stoppst bei 12. Die Schleife endet immer, denn a × b ist ein gemeinsames Vielfaches.

Die Anzahl der Versuche entspricht ungefähr der Größe der Antwort. Für die Primzahlen 46337 und 46327 lautet die Antwort 2146654199 – mehr als zwei Milliarden Versuche.

Algorithmus

Setze m auf den größeren Wert von a und b.
Solange m % a oder m % b nicht 0 ist, addiere 1 zu m.
Gib m zurück.

def lcm(a, b):
    m = max(a, b)
    while m % a != 0 or m % b != 0:
        m += 1
    return m

Gehe die Vielfachen der größeren Zahl durch

Idee

Die Antwort muss ein Vielfaches der größeren Zahl big sein. Gehe also in Schritten von big vor: big, 2 × big, 3 × big und so weiter, bis die kleinere Zahl die erste dieser Zahlen teilt. Für 4 und 6 probierst du 6 und dann 12.

Da small × big immer ein gemeinsames Vielfaches ist, läuft die Schleife höchstens min(a, b) Mal, hier also höchstens eine Million Mal. Für diese Grenzen ist das schnell genug, aber der Aufwand wächst dennoch mit der Eingabegröße; bei Zahlen bis zu 10^18 wäre das nicht der Fall.

Algorithmus

Sei big die größere Zahl und small die kleinere.
Setze m = big.
Solange m % small nicht 0 ist, addiere big zu m.
Gib m zurück.

def lcm(a, b):
    big, small = max(a, b), min(a, b)
    m = big
    while m % small != 0:
        m += big
    return m

Durch den ggT teilen, dann multiplizieren

Idee

Zerlege beide Zahlen in Primfaktoren. Für jede Primzahl nimmt der ggT die kleinere und das kgV die größere ihrer beiden Potenzen, sodass beide zusammen jeden Faktor von a und b genau einmal verwenden: gcd × lcm = a × b. Für 4 = 2² und 6 = 2 × 3 ist der ggT 2 und das kgV 2² × 3 = 12.

Der euklidische Algorithmus findet den ggT in O(log(min(a, b))) Schritten. Berechne dann a / gcd × b in dieser Reihenfolge: Der ggT teilt a ohne Rest, sodass nichts verloren geht und kein Zwischenschritt das Ergebnis übersteigt. a × b / gcd führt bei a = b = 10^6 zu einem Überlauf einer 32-Bit-Ganzzahl: Das Produkt ist 10^12, während das Ergebnis nur 10^6 beträgt.

Algorithmus

Kopiere a und b in x und y.
Solange y nicht 0 ist, ersetze (x, y) durch (y, x % y). Jetzt ist x der größte gemeinsame Teiler.
Teile a durch x.
Multipliziere das Ergebnis mit b und gib es zurück.

def lcm(a, b):
    x, y = a, b
    while y != 0:
        x, y = y, x % y
    # x is gcd(a, b). Divide before multiplying.
    return a // x * b

Stolperfallen und Grenzfälle

Zuerst a × b berechnen. In Java, C, C++, C# und Rust führt das Produkt zweier Zahlen nahe 10^6 zu einem Überlauf einer 32-Bit-Ganzzahl und ergibt einen falschen oder negativen Wert (ein Rust-Debug-Build löst eine Panic aus), obwohl das kgV in den Wertebereich passt.
Division mit Gleitkommazahlen. Das Ergebnis kann als 2.146654199E9 zurückkommen oder seine letzten Stellen verlieren; verwende durchgehend Ganzzahlen.
Euklids Schleife direkt mit a und b ausführen. Danach enthalten sie den ggT und 0, also arbeite mit Kopien.
Annehmen, dass das Ergebnis a × b ist. Das gilt nur, wenn die Zahlen keinen gemeinsamen Faktor haben: lcm(4, 6) ist 12, nicht 24.

Häufige Fragen3

Wie lautet die Formel für das kgV zweier Zahlen?

lcm(a, b) = a × b / gcd(a, b), berechnet als a / gcd(a, b) × b, damit kein Zwischenwert das Ergebnis überschreitet. Für 4 und 6 ist der gcd 2, und 4 / 2 × 6 = 12.

Wie hoch ist die Zeitkomplexität der Berechnung des kgV?

Mit der ggT-Formel beträgt die Laufzeit O(log(min(a, b))), also die Kosten des euklidischen Algorithmus, und der Speicherbedarf O(1). Das Durchlaufen der Vielfachen der größeren Zahl hat eine Laufzeit von O(min(a, b)), und das Zählen in Einerschritten hat eine Laufzeit von O(lcm(a, b)).

Wie findet man das kgV von mehr als zwei Zahlen?

Falte die Liste: lcm(a, b, c) = lcm(lcm(a, b), c). Für [4, 6, 10] gilt: lcm(4, 6) = 12 und lcm(12, 10) = 60. Der laufende Wert wächst schnell, verwende daher 64-Bit-Ganzzahlen, wenn die Liste lang ist.