Finden nächste Primzahl-Algorithmus

Ich freue mich zu verbessern, meinen Algorithmus zu finden, der nächste primenumber das Recht auf eine bestimmte Anzahl.
Was ich habe, so weit ist diese:

int NextPrime(int a)
{
    int i, j, count, num;
    for (i = a + 1; 1; i++)
    {
        for (j = 2, count = 0; j <= i; j++)
        {
            if (i%j == 0)
            {
                count++;
            }
        }
        if (count == 1)
        {
            return i;
            break;
        }
    }
}

Tho dieser Algorithmus ist nicht effizient beim laufen oft.
Kann mir jemand Ratschläge geben, wie der Algorithmus könnte beschleunigt oder verbessert.

  • en.wikipedia.org/wiki/Sieve_of_Eratosthenes
  • Die beiden basic-speed-ups zu erhöhen j mit 2 (ab 3, nach dem Test für 2), da nur ungerade zahlen außer 2 sind prim. Darüber hinaus nur überprüfen bis zu der Quadratwurzel der Anzahl (als einer der Faktoren für eine Zahl <= die Quadrat-Wurzel.)
  • siehe auch > diese Frage
  • Verwenden break; nach count++;.
  • Ich verstehe nicht, warum Menschen downvoting jede Frage. Dieses ist einfach urkomisch. Das Sieb des Eratosthenes ist nicht der richtige Weg hier.
  • Haben Sie versuchen zu tun, einige probabilistic primality tests vor dem start der innere Zyklus? en.wikipedia.org/wiki/Primality_test

InformationsquelleAutor Dark Side | 2015-05-05
  1. 9

    Sieb des Eratosthenes ist nicht die beste Lösung, wenn nur eine Primzahl, die gefunden werden sollen. Hier ist die Lösung, die nützlich für diesen Zweck. Es basiert auf der Idee, dass alle Primzahlen werden in form 6k+-1, so bin ich nur die Tests 2, 3 und zahlen in der form 6+-1. Natürlich, wird die Schleife beendet, wenn divisor Verstöße gegen sqrt(a), da alle diese zahlen sind bereits erfolgreich getestet worden.

    bool IsPrime(int number)
{

    if (number == 2 || number == 3)
        return true;

    if (number % 2 == 0 || number % 3 == 0)
        return false;

    int divisor = 6;
    while (divisor * divisor - 2 * divisor + 1 <= number)
    {

        if (number % (divisor - 1) == 0)
            return false;

        if (number % (divisor + 1) == 0)
            return false;

        divisor += 6;

    }

    return true;

}

int NextPrime(int a)
{

    while (!IsPrime(++a)) 
    { }
    return a;

}

    Ergebnis ist, dass diese Schleife funktioniert sehr schnell auf ein paar große Nummern, die ich ausprobiert habe.

    • Ja, danke. Behoben.
    • Funktion IsPrime funktioniert nicht immer richtig, zum Beispiel das Ergebnis für die Anzahl 64144081 = 8009 ^ 2 ist true.
    • Hi @AlexeiShestakov, vielen Dank für die Berichterstattung in diesem Fall. Eigentlich ist die Stopp-Bedingung ist falsch in meinem code - statt laufen während der divisor ^ 2 <= n -, loop-muss weiter while (divisor - 1) ^ 2 <= n. Große Fall der Randbedingung bug, ich Schreibe dies nieder! Und Sie haben ein +1 von mir.
    • Wenn Sie das Kontrollkästchen für 2 in NextPrime vor der while-Schleife, die Sie tun können ++++a, Zugabe von 2 statt 1, denn 2 ist die einzige noch prime.
    • Gute Idee, danke.
    InformationsquelleAutor Zoran Horvat
  2. 3

    Kann man verbessern auf das Sieb des Eratosthenes durch eine Menge, wenn Sie nur überprüfen Sie jede Zahl, die gegen jede prime, bevor es bis in die Wurzel der Primzahl. Für diese Sie benötigen, um eine Liste aller Primzahlen bis dann. Dies erhöht die Speicher Kosten, sondern erhöht die Ausführungsgeschwindigkeit durch eine lange erschossen.

    Pseudocode:

    List foundPrimes;
foundPrimes.add(1)
foundPrimes.add(2)

bool isPrime(int x) {
    for (int divisor in foundPrimes) {
        if (divisor*divisor > x) {
            foundPrimes.add(x);
            return true;
        } else if (x % divisor==0) {
            return false;
        }
    }
    //Invalid, need to run the algo from 3 on to fill the list
}

int nextPrime(int x) {
    while (!isPrime(++x)) {}
    return x;
}
    InformationsquelleAutor Dakkaron
Schreibe einen Kommentar