Komplexität von Druck ersten n Primzahl

Question

In einem Interview, das ich diese Fragen gegeben wurde:

Write a function to print first n prime numbers 

Die Funktion sieht wie folgt aus:

Live on ideone

while (true) { 
    boolean isPrime = true; 
    for (int divisor = 2; divisor <= (int)(Math.sqrt(number)); divisor++) { 
    if (number % divisor == 0) { 
     isPrime = false;  
     break; 
    } 
    } 
    number++; 
    if(isPrime) { 
    System.out.print(number + " "); 
    primes++; 
    } 

    if (primes == n) 
     break; 
} 

Eine einfache Komplexitätsanalyse führte könnte zu O(n√n)
Aber der Interviewer sagte, dass die Outerloop geht nicht einfach n bec Zum Beispiel, um die ersten 100 Primzahlen zu finden, die wir nach 541 (also die 100. Primzahlen) durchlaufen müssen.

Also, wie drücken wir die Zeitkomplexität aus?

Answer 1

Dies zu beantworten erfordert hohe Mathematik, nämlich das Verteilungsgesetz der Primzahlen. Es sagt Ihnen (https://en.wikipedia.org/wiki/Prime_number_theorem), dass der Wert der n -ten Primzahl ungefähr n.log(n) ist.

Dann ist Ihre Komplexität O(n√n.log(n)√log(n)).

---

Ich könnte sich herausstellen, dass diese Schranke pessimistisch ist, weil nicht alle Iterationen bis √n laufen. Zum Beispiel werden gerade Zahlen sofort erkannt. Für eine engere Grenze benötigen Sie das Verteilungsgesetz des kleinsten Faktors der ganzen Zahlen.