Wie finde ich die nächste Primzahl?

Question

Gibt es einen schönen Algorithmus, um die nächste Primzahl zu einer gegebenen real Nummer zu finden? Ich muss nur innerhalb der ersten 100 Primzahlen oder so suchen.

Derzeit habe ich eine Reihe von Primzahlen in einem Array gespeichert und ich überprüfe die Differenz eine Zahl auf einmal (O (n)?).

Answer 1

Anstatt eine sortierte Liste von Primzahlen, angesichts der relativ kleinen Bereich ausgerichtet, haben ein Array durch alle ungeraden Zahlen im Bereich indiziert (Sie wissen, es gibt keine geraden Primzahlen außer dem Sonderfall 2) und enthält die nächste prime. Das Finden der Lösung wird zu O (1) zeitweise.

Ich denke, die 100. Primzahl ist circa 541. Ein Array von 270 [kleinen] Ints ist alles was benötigt wird.

Dieser Ansatz ist insbesondere angesichts der relativ hohen Dichte von Primzahlen (insbesondere relativ zu ungeraden Zahlen) im Bereich unter 1.000 gültig. (Da dies die Größe eines Binärbaums beeinflusst)

Answer 2

Der einfachste Ansatz wäre, die Primzahlen in einer sortierten Liste zu speichern und Ihren Algorithmus für eine binäre Suche zu modifizieren.

Der standardmäßige binäre Suchalgorithmus würde null für einen Fehlversuch zurückgeben, aber es sollte einfach sein, ihn für Ihre Zwecke zu modifizieren.

Answer 3

Sie sollten Ihre Nummer in Array sortieren, dann können Sie binary search verwenden. Dieser Algorithmus ist im schlechtesten Fall O (log n) -Leistung.

Answer 4

Wenn Sie nur in den ersten 100 Primzahlen suchen müssen, erstellen Sie einfach eine sortierte Tabelle dieser Primzahlen und führen eine binäre Suche durch. Dies wird dich entweder zu einer Primzahl oder zu einem Punkt zwischen zwei bringen, und du prüfst, welcher davon näher ist.

Edit: Angesichts der Verteilung der Primzahlen in diesem Bereich könnten Sie wahrscheinlich beschleunigen (ein winziges bisschen) mit einer Interpolation Suche - anstatt immer in der Mitte der Tabelle, verwenden lineare Interpolation zu erraten ein genauerer Startpunkt. Die 100. Primzahl sollte ungefähr bei 250 liegen (bei einer Schätzung - ich habe das nicht überprüft), also wenn Sie zum Beispiel die am nächsten zu 50 haben wollten, würden Sie ungefähr 1/5 des Weges hinein starten das Array statt halbwegs. Sie können die Primzahlen so behandeln, dass sie bei 1 beginnen, also teilen Sie einfach die Nummer, die Sie wollen, durch die größte in Ihrem Bereich, um den Startpunkt zu schätzen.

Answer 5

Der schnellste Algorithmus? Erstellen Sie eine Nachschlagetabelle mit p [100] = 541 Elementen und geben Sie das Ergebnis für floor (x) zurück, mit spezieller Logik für x auf [2,3]. Das wäre O (1).

Answer 6

Die Antworten sind bei der gegebenen Aufgabe ziemlich kompliziert. Die ersten hundert Primzahlen are all less then 600. Ich würde ein Array der Größe 600 erstellen und jeweils den Wert der nächsten Primzahl zu dieser Nummer hinzufügen. Dann würde ich eine Zahl zum Testen geben, die ich mit den Funktionen floor und ceil nach oben und unten run- den würde, um eine oder zwei mögliche Antworten zu erhalten. Ein einfacher Vergleich mit den Entfernungen zu diesen Zahlen gibt Ihnen eine sehr schnelle Antwort.

Answer 7

Wenn Sie einen Algorithmus schreiben möchten, hat eine Wikipedia-Suche nach prime number mich zu einem anderen Artikel über die Sieve of Eratosthenes geführt. Der Algorithmus sieht ein bisschen einfach aus und ich denke, eine rekursive Funktion würde ihm gut passen. (Ich könnte mich irren.)

Answer 8

Wenn die Array-Lösung keine gültige Lösung für Sie ist (es ist die beste für Ihr Szenario), können Sie den folgenden Code versuchen. Nach dem "2 oder 3" -Fall wird jede ungerade Zahl vom Anfangswert bis zur Primzahl überprüft.

static int NearestPrime(double original) 
{ 
    int above = (int)Math.Ceiling(original); 
    int below = (int)Math.Floor(original); 

    if (above <= 2) 
    { 
     return 2; 
    } 

    if (below == 2) 
    { 
     return (original - 2 < 0.5) ? 2 : 3; 
    } 

    if (below % 2 == 0) below -= 1; 
    if (above % 2 == 0) above += 1; 

    double diffBelow = double.MaxValue, diffAbove = double.MaxValue; 

    for (; ; above += 2, below -= 2) 
    { 
     if (IsPrime(below)) 
     { 
      diffBelow = original - below; 
     } 

     if (IsPrime(above)) 
     { 
      diffAbove = above - original; 
     } 

     if (diffAbove != double.MaxValue || diffBelow != double.MaxValue) 
     { 
      break; 
     } 
    } 

    //edit to your liking for midpoint cases (4.0, 6.0, 9.0, etc) 
    return (int) (diffAbove < diffBelow ? above : below); 
} 

static bool IsPrime(int p) //intentionally incomplete due to checks in NearestPrime 
{ 
    for (int i = 3; i < Math.Sqrt(p); i += 2) 
    { 
     if (p % i == 0) 
      return false; 
    } 

    return true; 
} 

Answer 9

Lookup-Tabelle Jota Größe von 100 Bytes; (unsigned chars) Runde reelle Zahl und verwenden Sie Lookup-Tabelle.

Answer 10

Einfachste Antwort- Jede Primzahl kann in der Form (6 * x-1 und 6 * X +1) (außer 2 und 3) dargestellt werden. Let Nummer ist N.divide es mit 6. t = N/6; jetzt a = (t-1) * 6 b = (t + 1) * 6 und prüfen, welche näher an N. ist

Answer 11

public static boolean p(int n){ 

    for(int i=3;i*i<=n;i+=2) { 
     if(n%i==0) 
      return false; 
    } 
    return n%2==0? false: true; } 

public static void main(String args[]){ 
    String n="0"; 
    int x = Integer.parseInt(n); 
    int z=x; 
    int a=0; 
    int i=1; 
    while(!p(x)){ 

     a = i*(int)Math.pow(-1, i); 
     i++; 
     x+=a; 
    } 

    System.out.println((int) Math.abs(x-z));} 

dies für n> = 2 ist.

Answer 12

In Python:

>>> def nearest_prime(n): 
    incr = -1 
    multiplier = -1 
    count = 1 
    while True: 
     if prime(n): 
      return n 
     else: 
      n = n + incr 
      multiplier = multiplier * -1 
      count = count + 1 
      incr = multiplier * count 

>>> nearest_prime(3) 
3 
>>> nearest_prime(4) 
3 
>>> nearest_prime(5) 
5 
>>> nearest_prime(6) 
5 
>>> nearest_prime(7) 
7 
>>> nearest_prime(8) 
7 
>>> nearest_prime(9) 
7 
>>> nearest_prime(10) 
11 

Answer 13

<?php 
$N1Diff = null; 
$N2Diff = null; 

$n1 = null; 
$n2 = null; 

$number = 16; 

function isPrime($x) { 

    for ($i = 2; $i < $x; $i++) { 
     if ($x % $i == 0) { 
      return false; 
     } 
    } 

    return true; 
} 


for ($j = $number; ; $j--) { 

    if(isPrime($j)){ 
     $N1Diff = abs($number - $j); 
     $n1 = $j; 
     break; 
    } 
} 


for ($j = $number; ; $j++) { 

    if(isPrime($j)){ 
     $N2Diff = abs($number - $j); 
     $n2 = $j; 
     break; 
    } 

} 

if($N1Diff < $N2Diff) { 

    echo $n1; 

} else if ($N1Diff2 < $N1Diff){ 
    echo $n2; 
}