Drucken von Primzahlen in Java Rekursion
Schrieb ich eine ähnliche Funktion in C, und war in der Lage zu erreichen das gewünschte Ergebnis, im Gegensatz zu java.
Unten ist der code, der prüft, ob eine Zahl eine Primzahl ist rekursiv.
Zusammenstellung sagt, ich bin fehlt eine return-Anweisung.
Die Anzahl überprüft werden, ob eine prime x ist. Die variable i ist der divisor.(dh) x/2, (x/2)-1,...0.
public int primes(int x, int i)
{
if(i==0)
return 1;
if(x%i==0)
return 0;
else
primes(x, i-1);
}
Was ist die Komplexität dieser code, wenn ich musste zum drucken der ersten 1000 Primzahlen.
Für die Komplexität, die im schlimmsten Fall
Nein, es wird nicht amortisieren zu etwas kleiner, weil die Prüfung erfolgt in der falschen Reihenfolge. n=1000 Primzahlen bedeutet ~ N=8000 zahlen, um zu testen, indem Sie ein O(N^2) Algorithmus; seien Sie nicht so sicher, dass es zu schnell laufen, nur weil n=1000, scheint klein (haben Sie sagen, "trotzdem"...) - seine Komplexität ist grauenhaft (siehe z.B. Haskell test-Eintrag mit den entsprechenden Algorithmus zeigt ~ N^2.2 , ~ n^2.5 Laufzeit-Verhalten.
Ich hatte gedacht, OP
Sie Taten, sprechen über die Suche nach den ersten 1000 Primzahlen. und ich gab Ihnen Beweise, dass es wird schlimmer als N^2.
empirische Bestellungen von Wachstum Algorithmus ~ n^2.5, in n Primzahlen produziert.
i
verringert den ganzen Weg hinunter zu 0, also wenn i
beginnt bei x/2
, es ist etwa O(x). Aber das wird sich amortisieren, etwas viel kleiner, da offensichtlich nicht jeder Zahl eine Primzahl ist (en.wikipedia.org/wiki/Prime_number_theorem). Für Schlappe 1000 Primzahlen bezweifle ich, es wird sehr lange dauern, eh.Nein, es wird nicht amortisieren zu etwas kleiner, weil die Prüfung erfolgt in der falschen Reihenfolge. n=1000 Primzahlen bedeutet ~ N=8000 zahlen, um zu testen, indem Sie ein O(N^2) Algorithmus; seien Sie nicht so sicher, dass es zu schnell laufen, nur weil n=1000, scheint klein (haben Sie sagen, "trotzdem"...) - seine Komplexität ist grauenhaft (siehe z.B. Haskell test-Eintrag mit den entsprechenden Algorithmus zeigt ~ N^2.2 , ~ n^2.5 Laufzeit-Verhalten.
Ich hatte gedacht, OP
primes
ist O(x) (oder O(n) oder was auch immer). So sicher, ob er Schleifen es ist O(n^2), aber es ist nicht die absolute worst-case, da OP hat angegeben, er beginnt i
bei x/2
, so gleicht sich sofort fehl. Dann finden 1000 Primzahlen x
muss nur 7919, also Primzahlen nicht recurse sehr weit für die meisten zahlen.Sie Taten, sprechen über die Suche nach den ersten 1000 Primzahlen. und ich gab Ihnen Beweise, dass es wird schlimmer als N^2.
empirische Bestellungen von Wachstum Algorithmus ~ n^2.5, in n Primzahlen produziert.
InformationsquelleAutor Farveaz | 2014-07-22
Du musst angemeldet sein, um einen Kommentar abzugeben.
In diesem Fall:
Sind Sie nicht der Rückkehr nichts. Aber der compiler muss dafür sorgen, dass etwas zurückgegeben wird, in allen Fällen. Nur zurück, was den rekursiven Aufruf der Methode zurück:
Ändern Sie auch den ersten Fall ist Voraussetzung, um
i == 1
so gibt es1
auf Primzahlen richtig.InformationsquelleAutor rgettman
Auf den ersten Blick scheint es, dass Sie fehlt eine Rückkehr in Ihre else-Anweisung:
edit: Außerdem, wie gesagt, in rgettman Antwort, es gibt einen logischen Fehler in der ersten bedingten
if(i==0)
. Es sollteif(i==1)
. Nach dem testen der code mit dem oben edit, hier ist mein Ergebnis:InformationsquelleAutor Christian Wilkie
Brauchen Sie nur ein
return
in Ihremelse
.Den
return
es wird wieder die Ergebnisse der rekursiven Aufrufe, und Sie werden Ihren Weg in den stack. Obwohl, dies könnte führen zuStackOverflowException
s.InformationsquelleAutor krillgar
InformationsquelleAutor Tanvir Arafat
Können Sie die Logik:
Dann Anzeige
primeNumbers
.InformationsquelleAutor kirti
InformationsquelleAutor dummy
InformationsquelleAutor user8492094