Ich mache das Problem 7 des Projekts Euler. Was ich tun soll, ist die Berechnung der 10.001 st Primzahl. (Eine Primzahl ist eine ganze Zahl größer als eins, die nur durch sich selbst und eins teilbar ist.)
Hier ist mein aktuelles Programm:
%Vor%Es funktioniert gut mit dem Finden, sagen wir die 100 th Primzahl, aber das Laufen mit sehr großen Eingaben (wie beispielsweise 10.001) führt zu einem Stapelüberlauf. Warum und wie kann ich das beheben?
Ich denke, das Problem ist, dass Sie rekursiv Prime aufrufen, um zu bestimmen, ob eine Zahl prim ist oder nicht. Um also festzustellen, ob die Zahl 1000 prim ist oder nicht, rufen Sie Prime 1000 mal rekursiv auf. Jeder rekursive Aufruf erfordert, dass Daten auf dem Stapel gespeichert werden. Der Stack ist nur so groß, dass Sie auf dem Stack keinen Platz mehr haben, um rekursive Aufrufe zu tätigen. Verwenden Sie eine iterative Lösung anstelle einer rekursiven Lösung.
Sie sollten alle Primzahlen, die Sie bisher erhalten haben, in einer Nachschlage-Liste speichern. Sie werden also prüfen, ob die Zahl durch die Nummern dieser Liste geteilt ist. Wenn nicht, ist es eine Primzahl - geh und füge es der Liste hinzu.
Eine andere Idee ist, number++; durch number += 2; zu ersetzen und die Überprüfung von 3 zu starten, sobald gerade Zahlen mit Ausnahme für 2 nicht prim sind.
Ich habe dieses Problem kürzlich gelöst. Ich würde vorschlagen, Ihre Primzahlen mit einem Sieb von Eratosthenes zu erzeugen, sagen Sie alle Primzahlen & lt; 1 Million. Es ist kein harter Algorithmus zu implementieren, und es ist ziemlich schnell für die Anzahl der Primes, die Sie brauchen.
Compiler für einige Sprachen (z. B. viele funktionale und semi-funktionale Sprachen wie Lisp) werden die Tail-Rekursion, wie Sie sie verwendet haben, in Iteration konvertieren, aber (scheinbar) tut der Java-Compiler das nicht für Sie. Als Ergebnis verwendet jeder rekursive Aufruf Stack-Speicherplatz, und schließlich gehen Sie aus und der Stack überläuft.
Natürlich möchten Sie für die meisten Zwecke einen anderen Algorithmus verwenden - was Sie gerade verwenden, ist ziemlich schrecklich, wie diese Dinge gehen. Zumindest müssen Sie nur ungerade Zahlen bis zur Quadratwurzel der Zahl überprüfen, die Sie testen ...
Ihre Strategie, eine Primzahl zu testen, besteht darin, ihre Teilbarkeit mit jeder kleineren natürlichen Zahl zu prüfen.
Wenn Sie Ihre Strategie verschieben, um mit nur jeder kleineren Primzahl auf Teilbarkeit zu prüfen, würden Sie eine Menge Berechnung einsparen.
Um dies im Allgemeinen zu lösen, müssen Sie von einer rekursiven zu einer iterativen Lösung wechseln. (Jeder rekursive Algorithmus kann auch iterativ ausgedrückt werden.)
Da die Funktion Prime rekursiv ist, wird es immer ein Systemlimit geben, wie oft es sich selbst aufrufen kann.
Sie haben jedoch möglicherweise genug Speicher auf Ihrem System, um 10001 zu erreichen. Java ermöglicht es Ihnen, die maximale Speichermenge (Stapel, Heap usw.) festzulegen, die die VM verwendet. Erhöhen Sie die Stack-Speicher-Nummer, und Sie werden es wahrscheinlich schaffen können. Siehe diese Seite
für einige Java VM-Optionen.
Sie können immer den Rabin-Miller Primitivitätstest verwenden. Es ist ein sehr einfach zu implementierender Algorithmus und sehr schnell, obwohl zu verstehen, wie es funktioniert, ist ein bisschen härter.
Das Problem liegt in der rekursiv definierten Funktion Prime(X,Y) , aber auch im verwendeten Algorithmus. Es gibt nur so viel Rekursion Tiefe , die der Funktionsaufrufmechanismus von Java aufnehmen kann, bevor der Aufrufstapel erschöpft ist, was den Fehler "Stapelüberlauf" verursacht.
Es genügt, die Teilbarkeit auf alle Zahlen unterhalb der Quadratwurzel der zu testenden Zahl zu testen. Bezogen auf den OP-Code heißt das, nicht von Prime(N,N-1) , sondern von Prime( N, floor( sqrt( N+1)) ) zu starten. Diese Änderung allein könnte ausreichen, um den SO-Fehler für diese spezielle Aufgabe zu verhindern, da sich die Rekursionstiefe von 10000 auf nur 100 ändert.
Algorithmische Probleme beginnen nur dort. Der Prime(X,Y) -Code zählt down und testet die Zahl zuerst mit größeren Zahlen. Aber kleinere Faktoren werden viel häufiger gefunden; Das Zählen sollte vom kleinsten möglichen Faktor, 2 (der für 50% der Zahlen angetroffen wird), aufwärts bis zum sqrt der Kandidatennummer gemacht werden. Die Funktion sollte auch bei dieser Gelegenheit als einfache while -Schleife neu geschrieben werden.
Die nächste einfache und offensichtliche Verbesserung besteht darin, die geraden Zahlen ganz zu ignorieren. 2 ist bekannt, dass es eine Primzahl ist; Alle anderen Evens sind nicht. Das bedeutet, dass die Schleife von numberOfPrimes = 1; number = 3; gestartet und von number += 2 gezählt wird, um nur ungerade Zahlen zu zählen, wobei isPrime(N) ihre Teilbarkeit nur durch die ungeraden Zahlen in einer while -Schleife testet beginnend mit X = 3 , testet auf N % X und zählt nach X += 2 .
Oder in Pseudocode (eigentlich Haskell), der Originalcode ist
%Vor%das vorgeschlagene Update:
%Vor% Die angezeigten Zeiten beziehen sich auf nicht kompilierten Code in GHCi (auf einem langsamen Laptop). Empirische lokale Wachstumsreihenfolge als log(t2/t1) / log(n2/n1) . Noch schneller ist das Testen mit Primzahlen und nicht mit ungeraden Zahlen.
btw, Der Originalcode gibt nicht die 10001. Primzahl, sondern die darüber liegende Nummer aus.
Tags und Links java stack-overflow primes