Least Common Multiple
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.
Zum Beispiel sind die Vielfachen von 6 6, 12, 18, 24 und so weiter, die Vielfachen von 8 sind 8, 16, 24 und so weiter, und die erste Zahl auf beiden Listen ist 24.
Funktion
- 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 ≤ 1061 ≤ b ≤ 106- Die Antwort passt in eine vorzeichenbehaftete 32-Bit-Ganzzahl:
lcm(a, b) ≤ 231-1. Das Produkta × bmöglicherweise nicht.
Beispiele
- Eingabe
- a = 4b = 6
- Ausgabe
- 12
- Erklärung
- Die Vielfachen von
6beginnen mit 6, 12, 18; die Vielfachen von4beginnen mit 4, 8, 12. Die erste Zahl auf beiden Listen ist12.
- Eingabe
- a = 7b = 3
- Ausgabe
- 21
- Erklärung
7und3haben keinen gemeinsamen Faktor außer1, daher ist ihr kleinstes gemeinsames Vielfaches ihr Produkt,21.
- Eingabe
- a = 15b = 45
- Ausgabe
- 45
- Erklärung
15teilt45ohne Rest, daher ist45bereits ein gemeinsames Vielfaches, und es gibt kein kleineres Vielfaches von45.
+15 versteckte Tests beim Einreichen
Weiterführende Frage
Kannst du den größten gemeinsamen Teiler ganz ohne Division oder Restbildung finden, indem du nur subtrahierst und halbierst?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Die Antwort ist ein Vielfaches der größeren Zahl. Musst du jede Zahl dazwischen ausprobieren oder nur die Vielfachen der größeren Zahl?
Der größte gemeinsame Teiler und das kleinste gemeinsame Vielfache hängen zusammen:
gcd(a, b) × lcm(a, b) = a × b. Der euklidische Algorithmus findet den größten gemeinsamen Teiler in wenigen Dutzend Schritten.Berechne den ggT und gib dann
a / gcd × bzurück. Teile zuerst: Das Produkta × bkann einen 32-Bit-Integer überlaufen lassen, selbst wenn das Ergebnis in einen solchen passt.
Lösung
Das kleinste gemeinsame Vielfache und der größte gemeinsame Teiler sind zwei Seiten derselben Tatsache: gcd(a, b) × lcm(a, b) = a × b. Die schnelle Antwort lautet also a × b / gcd(a, b), mit einem Haken. Das Produkt kann 10^12 erreichen, was einen 32-Bit-Integer überlaufen lässt, selbst wenn das Ergebnis hineinpasst. Daher teilst du durch den ggT, bevor du multiplizierst.
Zähle ab der größeren Zahl weiter
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Die Antwort ist ein Vielfaches beider Zahlen und daher mindestens so groß wie die größere von ihnen. Setze einen Kandidaten m auf max(a, b) und erhöhe ihn um 1, bis sowohl a als auch b ihn teilen. Du probierst die Kandidaten in aufsteigender Reihenfolge aus, daher ist der erste passende der kleinste.
Für 4 und 6 probierst du 6, 7, 8, 9, 10 und 11 aus, die nicht funktionieren, und hörst bei 12 auf. 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 46337 und 46327, zwei Primzahlen, lautet die Antwort 2146654199, daher läuft die Schleife über zwei Milliarden Mal. Das ist viel zu langsam.
Algorithmus
- Setze
mauf den größeren Wert vonaundb. - Solange
m % aoderm % bnicht0ist, erhöhemum 1. - Gib
mzurück.
def lcm(a, b):
m = max(a, b)
while m % a != 0 or m % b != 0:
m += 1
return mGehe die Vielfachen der größeren Zahl durch
Idee
Die meisten Kandidaten beim Zählen sind aussichtslos: Die Antwort muss ein Vielfaches der größeren Zahl sein, nennen wir sie big. Springe also direkt von einem Vielfachen von big zum nächsten, big, 2 × big, 3 × big, und höre beim ersten auf, durch das die kleinere Zahl teilbar ist.
Für 4 und 6 probierst du 6 (4 teilt es nicht) und dann 12 (es teilt es). Die Antwort ist k × big für ein k, und k ist höchstens die kleinere Zahl, denn small × big ist immer ein gemeinsames Vielfaches. Die Schleife läuft also höchstens min(a, b) Mal, was hier niemals mehr als eine Million ist.
Das ist hier schnell genug, aber es wächst dennoch mit der Eingabe. Bei Zahlen bis zu 10^18 wäre das nicht der Fall.
Algorithmus
- Sei
bigdie größere Zahl undsmalldie kleinere. - Setze
m = big. - Solange
m % smallnicht0ist, addierebigzum. - Gib
mzurück.
def lcm(a, b):
big, small = max(a, b), min(a, b)
m = big
while m % small != 0:
m += big
return mDurch den ggT teilen und dann multiplizieren
Idee
Zerlege beide Zahlen in Primfaktoren. Der ggT nimmt jede Primzahl mit dem kleineren ihrer beiden Exponenten, das kgV nimmt den größeren, und zusammen verwenden sie jeden Faktor von a und von b genau einmal. Daraus folgt gcd(a, b) × lcm(a, b) = a × b, also lcm(a, b) = a × b / gcd(a, b). Für 4 = 2² und 6 = 2 × 3 ist der ggT 2 und das kgV 2² × 3 = 12.
Bestimme den ggT mit dem euklidischen Algorithmus: Ersetze (x, y) durch (y, x % y), bis y 0 ist. Das dauert O(log(min(a, b))) Schritte.
Berechne dann a / gcd × b, in dieser Reihenfolge. Der ggT teilt a ohne Rest, daher geht bei der Division nichts verloren, und das Ergebnis ist nie größer als die gesuchte Zahl. Die Berechnung von a × b / gcd führt bei a = b = 10^6 bei einer 32-Bit-Ganzzahl zum Überlauf: Das Produkt ist 10^12, während das Ergebnis nur 10^6 beträgt.
Algorithmus
- Kopiere
aundbinxundy. - Solange
ynicht0ist, ersetze(x, y)durch(y, x % y). Jetzt istxder ggT. - Teile
adurchx. - Multipliziere das Ergebnis mit
bund 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
Die Formel besteht aus einer Zeile, und die Fehler liegen in der Reihenfolge der Rechenoperationen.
- Zuerst
a × bberechnen. In Java, C, C++, C# und Rust läuft das Produkt zweier Zahlen nahe10^6bei einer 32-Bit-Ganzzahl über, und das Ergebnis ist falsch oder negativ (ein Rust-Debug-Build löst stattdessen eine Panic aus), obwohl das tatsächliche kgV hineinpasst. a × bdurch den ggT als Gleitkommazahl dividieren. Das Ergebnis kann als2.146654199E9zurückkommen oder seine letzten Ziffern verlieren; verwende durchgehend Ganzzahlen.- Den euklidischen Algorithmus direkt mit
aundbausführen und sie dann in der Formel verwenden. Nach der Schleife enthalten sie den ggT und0, also arbeite mit Kopien. - Annehmen, dass das Ergebnis
a × bist. Das gilt nur, wenn die beiden Zahlen keinen gemeinsamen Faktor haben:lcm(4, 6)ist12, nicht24.
Häufige Fragen4
Wie lautet die Formel für das kleinste gemeinsame Vielfache zweier Zahlen?
lcm(a, b) = a × b / gcd(a, b), berechnet als a / gcd(a, b) × b, damit der Zwischenwert nie größer als das Ergebnis ist. Für 4 und 6 ist der ggT 2, und 4 / 2 × 6 = 12.
Warum ist gcd(a, b) × lcm(a, b) gleich a × b?
Für jede Primzahl verwendet der ggT den kleineren ihrer Exponenten in a und b, und das kgV den größeren. Der kleinere plus der größere Exponent ergibt die Summe beider Exponenten, was genau dem Exponenten dieser Primzahl in a × b entspricht. Jede Primzahl stimmt überein, also sind die beiden Produkte gleich.
Wie hoch ist die Zeitkomplexität der Berechnung des kgV?
Mit der ggT-Formel beträgt der Aufwand O(log(min(a, b))), also der Aufwand des euklidischen Algorithmus, zuzüglich einer Division und einer Multiplikation. Dafür wird zusätzlicher Speicherplatz von O(1) benötigt. Die Suche durch Vielfache ist deutlich langsamer: O(min(a, b)), wenn du in Schritten der größeren Zahl vorgehst, und O(lcm(a, b)), wenn du in Einerschritten zählst.
Wie berechnet man das kleinste gemeinsame Vielfache von mehr als zwei Zahlen?
Falte die Liste zusammen: 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, achte daher auf einen Überlauf und verwende 64-Bit-Ganzzahlen, wenn die Liste lang ist.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def lcm(a, b):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
a = 4 b = 6
Erwartet
12