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 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

Schreibe einen Kommentar