Ich versuche, einen Code zu implementieren, der die Summe aller Primzahlen unter 2 Millionen zurückgibt. Ich habe eine isPrime (int x) -Methode, die wahr zurückgibt, wenn die Zahl prim ist. Hier ist es:
%Vor%Und die andere Methode, die ich rekursiv zu implementieren versuche, funktioniert nur bis zu einer bestimmten Zahl, über diese Nummer und ich bekomme einen Stack-Überlauffehler. Der höchste Code, mit dem ich arbeiten konnte, war 10.000.
Hier ist es:
%Vor%Warum bekomme ich einen Stapelüberlauffehler, wenn die Zahl größer wird und wie kann ich damit umgehen? Wie gehen Sie normalerweise mit dem Schreiben von Code für solche großen Zahlen um? IE: normale Nummer Operationen wie diese, aber für größere Zahlen? Ich schrieb das rekursiv, weil ich dachte, es wäre effizienter, aber es funktioniert immer noch nicht.
Ihre isPrime Funktion ist ineffizient, sie muss nicht in x gehen, es reicht aus, zur Quadratwurzel von x zu gehen.
Aber das ist nicht der Grund, warum Ihre Lösung nicht funktioniert. Sie können keine Rekursionstiefe von 1 Million haben.
Ich würde dieses Problem iterativ lösen, indem ich das Sieb von Eratosthenes und für die Schleife über das resultierende boolean -Array verwende.
Wenn Sie die Rekursion weiterhin verwenden möchten, können Sie die Tail-Rekursion verwenden. Bei der Rekursion wird jeder Funktionsaufruf einige Daten an den Stack senden, was begrenzt ist, wodurch ein Stapelüberlauffehler erzeugt wird. Bei der Tail-Rekursion werden Sie nichts auf den Stapel schieben und die Ausnahme nicht auslösen.
Grundsätzlich brauchen Sie nur die Daten der vorherigen Berechnung als Parameter zu senden, anstatt sie auf dem Stapel zu haben.
Also:
%Vor%mit Tail-Rekursion wäre
%Vor%Denken Sie daran, das ist nur Pseudo-Code nicht wirklich Java-Code, aber ist nahe genug an den Java-Code.
Weitere Informationen finden Sie unter
Sieb von Eratosthenes verwenden: -
Es folgt der Algorithmus, um alle Primzahlen zu finden, die kleiner oder gleich einer gegebenen Ganzzahl n sind, nach der Methode von Eratosthenes:
1) Erstellen Sie eine Liste aufeinanderfolgender Ganzzahlen von 2 bis n: (2, 3, 4, ..., n).
2) Zunächst sei p gleich 2, die erste Primzahl.
3) Ausgehend von p, zählen Sie in Schritten von p und markieren Sie jede dieser Zahlen größer als p selbst in der Liste. Diese Nummern sind 2p, 3p, 4p etc .; Beachten Sie, dass einige von ihnen bereits markiert wurden.
4) Finden Sie die erste Zahl größer als p in der Liste, die nicht markiert ist. Wenn es keine solche Nummer gab, hör auf. Ansonsten sei p nun gleich dieser Zahl (was die nächste Primzahl ist) und wiederhole ab Schritt 3.