Ich schaute mich um und fand andere Fragen, die Antworten enthielten, aber keine von ihnen befasste sich mit dem Umfang dieser speziellen Frage, einschließlich diese Frage , und auch dieser .
Ich muss das LCM großer Zahlenbereiche effizient berechnen. Ich habe mich bei diesen anderen Fragen nicht vertieft, da sie sich nicht mit Zahlenbereichen befassen, die so groß sind wie die, die dieser Algorithmus verarbeiten muss.
Der Code, den ich jetzt habe, kann den LCM jeder Zahl zwischen 1 und 350000 in ungefähr 90 Sekunden berechnen. (Die resultierende Zahl ist etwa 76000 Dezimalstellen lang). Ich hoffe, dass ich es irgendwann über Millionen oder sogar Milliarden von Elementen skalieren kann.
Es wird wahrscheinlich paralellisiert werden. Mit einigen Algorithmen wird dies gar nicht so schwierig sein, für andere wird es schwieriger (wenn der Algorithmus zum Beispiel das aktuell erzeugte LCM verwendet, um die Primalität für andere Teile seiner Berechnung zu berechnen)
Hier ist es:
%Vor%Beachten Sie, dass diese Funktion im Gegensatz zu einer typischen for-Schleife über [untere, obere] anstelle von [untere, obere] arbeitet. Dieses Verhalten ist beabsichtigt.
Ein bisschen unterstützende Mathematik ist, dass das LCM einer Menge von Zahlenprodukt der Menge von Primfaktoren ist, aus der irgendeine der Zahlen erzeugt werden kann, ohne irgendeine Außenseite des Pools zu erfordern. Wenn mein Bereich [1,20] ist, kann ich das auf folgende Weise darstellen:
%Vor%Gibt es effizientere Möglichkeiten, ein LCM über einen so großen Bereich zu berechnen?
Es ist mir egal, ob der Algorithmus, den jemand vorschlägt, sehr speicherintensiv ist, die Zeitleistung ist viel wichtiger (und auch teurer) als die Speicherleistung in diesem Fall.
Dies ist keine Hausaufgabenfrage.
Was ist der effizienteste Weg, um das LCM eines sehr großen Zahlenbereichs zu berechnen? Dieser Algorithmus muss auf untragbar große Zahlenbereiche angewendet werden und muss daher sorgfältig optimiert werden.
Eine naheliegende Frage ist: Was ist der effizienteste Weg, um den Logarithmus eines BigIntegers zu berechnen (Basis eines anderen BigIntegers)? Der resultierende Wert kann auf die nächste ganze Zahl abgeschnitten werden.
Dies ist das Layout des Algorithmus. Ich gehe davon aus, dass du immer bei 1 beginnst:
Finde Primzahlen im Bereich. Sie können das Eratosthenes-Sieb für 350000 verwenden. Für einen größeren Zahlenbereich benötigen Sie segmentiertes Sieb .
Verwenden Sie für jede Primzahl p die logarithmische Funktion, um den größten Exponenten e zu finden, bei dem p e innerhalb des Bereichs liegt. Multiplizieren Sie p e mit dem LCM. (Die Optimierungsdetails hängen von Ihrer Implementierung ab)
Warum ist das richtig?
<2>
sub> 2 ... p e n (wobei p ist sind paarweise unterschiedliche Primzahlzahlen und e (1), die größer oder gleich p i sup> (für alle i von 1 bis n). Da p
Dies ist eine Verallgemeinerung der Antwort von @nhahtdh
Zuerst finden Sie alle Primzahlen, die kleiner oder gleich der oberen Grenze sind.
Nehmen Sie dann jedes Primzahl p und notieren Sie die untere und obere Grenze in einer Basis-p-Notation. Die höchste Ziffer, die in den beiden Zahlen unterschiedlich ist, ist der Exponent von p, den Sie in Ihr LCM aufnehmen müssen. Wenn die untere Grenze 1 ist, ist dies trivialerweise die gleiche wie die andere Antwort.
Beachten Sie, dass die Komplexität dieses Algorithmus nicht von der Länge des Bereichs abhängt, sondern nur von der Größe der oberen Grenze.
Tags und Links algorithm java optimization biginteger lcm