Welcher ist der schnellste Algorithmus, um Primzahlen zu finden?

Das ist der Schnellste Algorithmus, um herauszufinden, Primzahlen mit C++? Ich habe verwendet sieve-Algorithmus, aber ich immer noch wollen, dass es schneller!

InformationsquelleAutor der Frage kasperasky | 2009-01-17

  1. 70

    Eine sehr schnelle Umsetzung der Sieb des Atkin ist Dan Bernstein ' s primegen. Dieses Sieb ist effizienter als die Sieb des Eratosthenes. Seine Seite hat einige benchmark-Informationen.

    InformationsquelleAutor der Antwort Greg Hewgill

  2. 26

    Wenn es wirklich schnell sein, können Sie auch eine Liste von Primzahlen:

    http://www.bigprimes.net/archive/prime/

    Wenn Sie müssen nur wissen, ob eine bestimmte Zahl eine Primzahl ist, gibt es verschiedene prime-tests aufgelistet auf wikipedia. Sie sind wahrscheinlich die Schnellste Methode, um zu bestimmen, wenn große zahlen sind Primzahlen, vor allem, weil Sie kann Ihnen sagen, ob eine Zahl nicht eine Primzahl ist.

    InformationsquelleAutor der Antwort Georg Schölly

  3. 23

    Er, ich weiß, ich bin eine Frage, die der Nekromant Antworten auf alte Fragen, aber ich habe gerade gefunden diese Frage suchen im Netz nach Möglichkeiten, effizient zu implementieren Primzahlen-tests.

    Bis jetzt, glaube ich, dass die Schnellste Primzahl-Test-Algorithmus ist Stark Wahrscheinlich Prime (SPRP). Ich zitiere von Nvidia CUDA Foren:

    Einer der mehr praktische Nische Probleme in der Zahlentheorie zu tun hat
    mit der Identifizierung von Primzahlen. Gegeben N, wie kann man effizient
    bestimmen Sie, ob es eine Primzahl ist oder nicht? Dies ist nicht nur ein thoeretical
    problem, kann es einen echten Bedarf im code, vielleicht, wenn Sie müssen
    dynamisch finden Sie eine prime-hash-Tabelle der Größe in bestimmten Bereichen. Wenn N
    ist etwas in der Größenordnung von 2^30, tun Sie wirklich wollen, zu tun 30000
    die division tests zur Suche für alle Faktoren? Offensichtlich nicht.

    Die gemeinsame praktische Lösung für dieses problem ist ein einfacher test genannt
    eine Euler wahrscheinlich prime test und einen stärkeren Generalisierung
    namens einer Starken Probable Prime (SPRP). Dies ist ein test, der für eine
    ganze Zahl N kann probabilistisch einstufen als prime oder nicht, und
    wiederholte tests erhöhen die Korrektheit Wahrscheinlichkeit. Der langsame Teil
    der test selbst umfasst hauptsächlich das berechnen eines Werts ähnlich
    A^(N-1) modulo N. Jemand der Implementierung von RSA-public-key-Verschlüsselung
    Variante (N) hat sich mit diesem Algorithmus. Es ist nützlich, sowohl für große Ganzzahlen
    (wie 512 bit) als auch normale 32-oder 64-bit-ints.

    Den test geändert werden kann, die eine probabilistische Ablehnung in eine
    der endgültige Beweis primality von precomputing bestimmte test-Eingang
    Parameter, die bekannt sind, um immer erfolgreich für Bereiche N.
    Leider ist die Entdeckung dieser "besten bekannten tests" ist effektiv
    eine Suche nach einem großen (eigentlich unendlich) - Domäne. Im Jahr 1980, eine erste Liste von
    nützliche tests wurde von Carl Pomerance (berühmt für die one
    zu Faktor RSA-129 mit seiner Quadratischen Seive-Algorithmus.) Später Jaeschke
    verbessert die Ergebnisse erheblich in 1993. Im Jahr 2004, Zhang und Tang
    verbessert die Theorie und die Grenzen des such-domain. Greathouse-und
    Livingstone veröffentlicht haben die meisten modernen Ergebnisse bis jetzt auf der
    web, auf http://math.crg4.com/primes.html, die besten Ergebnisse von einem riesigen
    search-domain an.

    Siehe hier für mehr info:
    http://primes.utm.edu/prove/prove2_3.html und http://forums.nvidia.com/index.php?showtopic=70483

    Wenn Sie müssen nur einen Weg zur Erzeugung von sehr großen Primzahlen und kümmern sich nicht um die Generierung aller Primzahlen < eine ganze Zahl n, die Sie verwenden können, Lucas-Lehmer-test, um zu überprüfen, Mersenne Primzahlen. Eine Mersenne-Zahl in der form 2^p-1. Ich denke, dass Lucas-Lehmer-test ist der Schnellste Algorithmus entdeckt für Mersenne-zahlen.

    Und wenn Sie nicht nur wollen, verwenden Sie die Schnellste Algorithmus, aber auch die Schnellste hardware hat, versuchen Sie es zu implementieren, mithilfe von Nvidia CUDA, schreiben einen kernel für CUDA und führen Sie es auf der GPU.

    Können Sie sogar Geld verdienen, wenn Sie entdecken groß genug Primzahlen, EFF gibt Preise von $50K $250K:
    https://www.eff.org/awards/coop

    InformationsquelleAutor der Antwort Mack

  4. 11

    Es ist ein 100% mathematischen test, der prüft, ob eine Zahl P eine Primzahl ist oder nicht, genannt AKS Primality Test.

    Das Konzept ist einfach: gegeben sei eine Zahl Pwenn alle Koeffizienten von (x-1)^P - (x^P-1) sind teilbar durch Pdann P eine Primzahl ist, andernfalls ist es eine zusammengesetzte Zahl.

    Beispielsweise gegeben P = 3hätte das Polynom:

       (x-1)^3 - (x^3 - 1)
 = x^3 + 3x^2 - 3x - 1 - (x^3 - 1)
 = 3x^2 - 3x

    Und die Koeffizienten sind beide teilbar durch 3 daher die Zahl eine Primzahl ist.

    Beispiel und wo P = 4die NICHT eine Primzahl ergeben würde:

       (x-1)^4 - (x^4-1)
 = x^4 - 4x^3 + 6x^2 - 4x + 1 - (x^4 - 1)
 = -4x^3 + 6x^2 - 4x

    Und hier können wir sehen, dass die Koeffizienten 6 ist nicht teilbar durch 4 daher ist es NICHT prim.

    Das Polynom (x-1)^P wird P+1 Bedingungen und entdeckt werden können Kombination. Also, dieser test wird in O(n) Laufzeit, also ich weiß nicht, wie sinnvoll das wäre, da kann man einfach Durchlaufen i von 0 bis p und Prüfung für den Rest.

    InformationsquelleAutor der Antwort Kousha

  5. 5

    Ist dein problem, zu entscheiden, ob eine bestimmte Zahl eine Primzahl ist? Dann brauchen Sie eine primality test (leicht). Oder wollen Sie alle Primzahlen bis zu einer gegebenen Zahl ist? In diesem Fall prime durchsiebt gut sind (einfach, aber erfordern Speicher). Oder benötigen Sie die Primfaktoren einer Zahl? Dies würde erfordern, die Faktorisierung (schwierig für große zahlen, wenn Sie wirklich wollen, dass die effizientesten Methoden). Wie groß sind die zahlen, die Sie suchen? 16 bit? 32 bit? größer?

    Einer cleveren und effizienten Weise zu pre-compute-Tabellen von Primzahlen, und halten Sie Sie in eine Datei mit einem bit-level-Codierung. Die Datei wird als eine lange bit-Vektor in der Erwägung, dass bit n repräsentiert die ganze Zahl n ist. Wenn n eine Primzahl ist, dessen bit gesetzt ist und null sonst. Lookup ist sehr schnell (Sie berechnen den byte-offset und eine bit-Maske) und benötigt nicht das laden der Datei im Speicher.

    InformationsquelleAutor der Antwort Christian Lindig

  6. 2

    Hängt es von Ihrer Anwendung. Es gibt einige überlegungen:

    • Brauchen Sie nur die information, ob ein paar zahlen Primzahlen sind, benötigen Sie alle Primzahlen bis zu einer bestimmten Grenze, oder benötigen Sie (potentiell) alle Primzahlen?
    • Wie groß sind die zahlen, die Sie zu bewältigen haben?

    Den Miller-Rabin-und Analog-tests, die sind nur schneller als ein Sieb für zahlen über einer bestimmten Größe (irgendwo um ein paar Millionen, glaube ich). Unten, mit einem trial-division (wenn Sie nur ein paar zahlen) oder ein Sieb ist schneller.

    InformationsquelleAutor der Antwort Svante

  7. 2

    Rabin-Miller ist ein standard probabilistic primality test. (Sie führen es K-mal und die Eingabe-Zahl ist entweder definitiv composite, oder es ist wahrscheinlich prim mit Fehlerwahrscheinlichkeit 4K. (ein paar hundert Iterationen, und es ist fast sicher sagen Sie die Wahrheit)

    Gibt es eine nicht-probabilistische (deterministisch) Variante des Rabin-Miller.

    Den Great Internet Mersenne Prime Search (GIMPS), die gefunden hat, den Weltrekord für die größte bewährten prime (274,207,281 - 1. Juni 2017), verwendet mehrere algorithmenaber dies sind die Primzahlen, die in speziellen Formen. Aber die GIMPS-Seite oben enthält einige Allgemeine deterministische primality tests. Sie erscheinen, um anzuzeigen, welcher Algorithmus ist "Schnellste" hängt von der Größe der Zahl getestet werden. Wenn Ihre Zahl passt in 64 bit, dann sollten Sie wahrscheinlich nicht verwenden eine Methode sollte die Arbeit auf Primzahlen mit mehreren Millionen stellen.

    InformationsquelleAutor der Antwort Jason S

  8. -1

    Ich immer verwenden Sie diese Methode für die Berechnung der folgenden zahlen Primzahlen mit dem Sieb-Algorithmus. 

    void primelist()
 {
   for(int i = 4; i < pr; i += 2) mark[ i ] = false;
   for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true;
   for(int i = 3, sq = sqrt( pr ); i < sq; i += 2)
       if(mark[ i ])
          for(int j = i << 1; j < pr; j += i) mark[ j ] = false;
  prime[ 0 ] = 2; ind = 1;
  for(int i = 3; i < pr; i += 2)
    if(mark[ i ]) ind++; printf("%d\n", ind);
 }

    InformationsquelleAutor der Antwort Osman Goni Nahid

  9. -3
    #include<stdio.h>
main()
{
    long long unsigned x,y,b,z,e,r,c;
    scanf("%llu",&x);
    if(x<2)return 0;
    scanf("%llu",&y);
    if(y<x)return 0;
    if(x==2)printf("|2");
    if(x%2==0)x+=1;
    if(y%2==0)y-=1;
    for(b=x;b<=y;b+=2)
    {
        z=b;e=0;
        for(c=2;c*c<=z;c++)
        {
            if(z%c==0)e++;
            if(e>0)z=3;
        }
        if(e==0)
        {
            printf("|%llu",z);
            r+=1;
        }
    }
    printf("|\n%llu outputs...\n",r);
    scanf("%llu",&r);
}

    InformationsquelleAutor der Antwort Tjandra

  10. -4
    #include <iostream>

using namespace std;

int set [1000000];

int main (){

    for (int i=0; i<1000000; i++){
        set [i] = 0;
    }
    int set_size= 1000;
    set [set_size];
    set [0] = 2;
    set [1] = 3;
    int Ps = 0;
    int last = 2;

    cout << 2 << " " << 3 << " ";

    for (int n=1; n<10000; n++){
        int t = 0;
        Ps = (n%2)+1+(3*n);
        for (int i=0; i==i; i++){
            if (set [i] == 0) break;
            if (Ps%set[i]==0){
                t=1;
                break;
            }
        }
        if (t==0){
            cout << Ps << " ";
            set [last] = Ps;
            last++;
        }
    }
    //cout << last << endl;


    cout << endl;

    system ("pause");
    return 0;
}

    InformationsquelleAutor der Antwort vidura

  11. -4

    Ich weiß, es ist etwas später, aber dies könnte nützlich sein für die Menschen, die hier ankommen, aus sucht. Wie auch immer, hier einige JavaScript, die sich auf die Tatsache, dass nur die wichtigsten Faktoren geprüft werden müssen, so dass die früher Primzahlen erzeugt durch den code wieder verwendet als test-Faktoren für spätere. Natürlich alle selbst und mod 5 Werte herausgefiltert, die erste. Das Ergebnis wird im array P, und dieser code kann crunch 10 Millionen Primzahlen, die in unter 1,5 Sekunden auf einem i7-PC (oder 100 Millionen, die in über 20). Umgeschrieben in C sollte es sehr schnell.

    var P = [1, 2], j, k, l = 3

for (k = 3 ; k < 10000000 ; k += 2)
{
  loop: if (++l < 5)
  {
    for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j)
      if (k % P[j] == 0) break loop

    P[P.length] = k
  }
  else l = 0
}

    InformationsquelleAutor der Antwort Robin Nixon

  12. -12
    #include<iostream>
using namespace std;

void main()
{
    int num,i,j,prime;
    cout<<"Enter the upper limit :";
    cin>>num;

    cout<<"Prime numbers till "<<num<<" are :2, ";

    for(i=3;i<=num;i++)
    {
        prime=1;
        for(j=2;j<i;j++)
        {
            if(i%j==0)
            {
                prime=0;
                break;
            }
        }

        if(prime==1)
            cout<<i<<", ";

    }
}

    InformationsquelleAutor der Antwort Gaurav

Schreibe einen Kommentar