Interview Frage: Was ist der schnellste Weg, um Primzahl rekursiv zu generieren?

Question

Die Generierung der Primzahl ist einfach, aber wie findet man sie am schnellsten und rekursiv (Primzahlen)?

Hier ist meine Lösung. Es ist jedoch nicht der beste Weg. Ich denke, es ist O (N * sqrt (N)). Bitte korrigieren Sie mich, wenn ich falsch liege.

public static boolean isPrime(int n) { 
     if (n < 2) { 
      return false; 
     } else if (n % 2 == 0 & n != 2) { 
      return false; 
     } else { 
      return isPrime(n, (int) Math.sqrt(n)); 
     } 
    } 

    private static boolean isPrime(int n, int i) { 
     if (i < 2) { 
      return true; 
     } else if (n % i == 0) { 
      return false; 
     } else { 
      return isPrime(n, --i); 
     } 
    } 

    public static void generatePrimes(int n){ 
     if(n < 2) { 
      return ; 
     } else if(isPrime(n)) { 
      System.out.println(n); 
     } 

     generatePrimes(--n); 

    } 

    public static void main(String[] args) { 

     generatePrimes(200); 
    } 

Answer 1

Für recurrsion sollten Sie memoization verwenden Ihre rekursive Funktion zu verbessern, bedeutet, wenn Sie Primzahl speichert es in einem Array zu finden, und im Aufruf von isPrime(n) zunächst prüfen, die Zahl in dem Feld liegt vor, wenn nicht zu isPrime nennen (n, (int) Math.sqrt (n)). Auch wenn isPrime (n, i) true zurückgibt, füge es zur prime-Liste hinzu, es ist besser, dein Array nach binärer Suche zu sortieren, in C# gibt es eine sortierte Liste, und die binäre Suchoperation benötigt 0 (n log n) und suchen ist O (log (n))] ich wusste nicht über Java [aber Sie können es implementieren].

Bearbeiten: Ihre aktuelle Vorgehensweise ist O(n sqrt(n)), aber mit meinem approch kann es in der gleichen Reihenfolge sein! aber bessere Leistung, in der Tat ist die Reihenfolge O(n sqrt(n)/log (n) + n log(n/log(n))) und weil Log (n) ist kleiner als n^Epsilon, ist es besser zu sagen, es ist O(n sqrt(n)) aber wie Sie sehen können, wird es log (n) Zeit schneller laufen.

Auch ist es besser i-2 nicht i-- und einige zusätzliche Check-in Start Algorithmus 2 * log (n) Zeit schneller ausführen.

Answer 2

Warum rekursiv?

Verwenden Sie bessere Primzahl Generation Algorithmus wie Sieb von Eratosthenes oder noch besser Sieve von Atkin.

Answer 3

In der Mathematik ist das Sieb von Atkin ein schneller, moderner Algorithmus zum Auffinden aller Primzahlen bis zu einer bestimmten Ganzzahl.

Wikipedia article (enthält Pseudo-Code)

Um dies rekursiv zu Adresse, zu tun, vielleicht die Sieve of Eratosthenes rekursiv implementiert werden kann. Diese page könnte hilfreich sein, da sie eine rekursive Implementierung zu diskutieren scheint.

Answer 4

Erstens, wenn Sie wollen große prime Zahlen erzeugen (im Gegensatz ganze Zahlen für primality zu testen) dann Pocklington's theorem ist praktisch. Dieser Theorem erlaubt einen schnellen Primalitätstest für einen Kandidaten p, wenn Sie genügend Primfaktoren von p-1 kennen. Daher ist die folgende Methode möglich: Erzeugen Sie einige Primzahlen, berechnen Sie ein geeignetes Vielfaches ihres Produkts und testen Sie mit dem Pocklington-Theorem. Wenn Sie große Primzahlen finden möchten (z.B. für das RSA-Kryptosystem), müssen Sie diese Methode rekursiv anwenden, um die Faktoren von p-1 zu erzeugen.

Die obige Beschreibung fehlt einige Details. Aber die Methode wurde gründlich analysiert. Ich denke, dieses Papier war die schnellste Methode, wenn wenn veröffentlicht wurde, obwohl einige Zeit seitdem gegangen ist und jemand könnte es verbessert haben.

P.Mihailescu. "Schnelle Erzeugung von nachweisbaren Primzahlen unter Verwendung der Suche in arithmetischen Progressionen", Proceedings CRYPTO 94, Vorlesungsnotizen in Computer Science, Band 939, Springer 1994, S. 282-293.

Answer 5

Was Sie brauchen, das Sieb des immer, hier ist der Code für eine rekursive Prime-Tester, ich denke, es ist sehr effizient, weil es nur die Primfaktoren testen muss, lassen Sie mich wissen, was Sie denken;)

von Ich würde es nicht mit etwas über einem Byte versuchen, es scheint eine Weile mit etwas über 100 zu dauern.