Welches ist der schnellste Algorithmus, um Primzahlen zu finden?

Welches ist der schnellste Algorithmus, um Primzahlen mit C ++ herauszufinden? Ich habe den Sieb-Algorithmus verwendet, möchte aber trotzdem, dass er schneller ist!

Eine sehr schnelle Implementierung des Siebs von Atkin ist Dan Bernsteins Primegen . Dieses Sieb ist effizienter als das Eratosthenes-Sieb . Seine Seite enthält einige Benchmark-Informationen.

Wenn es wirklich schnell gehen muss, können Sie eine Liste von Primzahlen hinzufügen:
http://www.bigprimes.net/archive/prime/

Wenn Sie nur wissen müssen, ob eine bestimmte Zahl eine Primzahl ist, finden Sie auf Wikipedia verschiedene Primzahlen . Sie sind wahrscheinlich die schnellste Methode, um festzustellen, ob große Zahlen Primzahlen sind, insbesondere weil sie Ihnen sagen können, ob eine Zahl keine Primzahl ist.

Er, er, ich weiß, ich bin ein Nekromant, der auf alte Fragen antwortet, aber ich habe gerade diese Frage gefunden, die im Internet nach Möglichkeiten sucht, effiziente Primzahlentests durchzuführen.

Bis jetzt glaube ich, dass der schnellste Primzahl-Testalgorithmus Strong Probable Prime (SPRP) ist. Ich zitiere aus Nvidia CUDA-Foren:

Eines der praktischeren Nischenprobleme in der Zahlentheorie hat mit der Identifizierung von Primzahlen zu tun. Wie können Sie bei N effizient feststellen, ob es sich um eine Primzahl handelt oder nicht? Dies ist nicht nur ein theoretisches Problem, es kann auch ein echtes Problem sein, das im Code benötigt wird, möglicherweise wenn Sie dynamisch eine Prime-Hash-Tabellengröße innerhalb bestimmter Bereiche finden müssen. Wenn N etwas in der Größenordnung von 2 ^ 30 ist, möchten Sie wirklich 30000 Teilungstests durchführen, um nach Faktoren zu suchen? Offensichtlich nicht.

Die übliche praktische Lösung für dieses Problem ist ein einfacher Test, der als Euler Probable Prime Test bezeichnet wird, und eine leistungsfähigere Verallgemeinerung, die als Strong Probable Prime (SPRP) bezeichnet wird. Dies ist ein Test, der für eine ganze Zahl N wahrscheinlich als Primzahl klassifiziert werden kann oder nicht, und wiederholte Tests können die Korrektheitswahrscheinlichkeit erhöhen. Der langsame Teil des Tests selbst besteht hauptsächlich darin, einen Wert zu berechnen, der A ^ (N-1) modulo N ähnlich ist. Jeder, der RSA-Verschlüsselungsvarianten mit öffentlichem Schlüssel implementiert, hat diesen Algorithmus verwendet. Es ist sowohl für große Ganzzahlen (wie 512 Bit) als auch für normale 32- oder 64-Bit-Ints nützlich.

Der Test kann von einer probabilistischen Zurückweisung in einen endgültigen Beweis der Primalität geändert werden, indem bestimmte Testeingabeparameter vorberechnet werden, von denen bekannt ist, dass sie für Bereiche von N immer erfolgreich sind. Leider ist die Entdeckung dieser "bekanntesten Tests" effektiv eine Suche nach einem großen ( in der Tat unendlich) Domäne. 1980 erstellte Carl Pomerance (bekannt dafür, dass er RSA-129 mit seinem quadratischen Seive-Algorithmus faktorisiert) eine erste Liste nützlicher Tests. Später verbesserte Jaeschke die Ergebnisse 1993 erheblich. 2004 verbesserten Zhang und Tang die Theorie und Grenzen der Suchdomäne. Greathouse und Livingstone haben die bislang modernsten Ergebnisse im Internet unter http://math.crg4.com/primes.html veröffentlicht , den besten Ergebnissen einer riesigen Suchdomäne.

Weitere Informationen finden Sie hier: http://primes.utm.edu/prove/prove2_3.html und http://forums.nvidia.com/index.php?showtopic=70483

Wenn Sie nur eine Möglichkeit benötigen, sehr große Primzahlen zu generieren, und nicht alle Primzahlen <eine ganze Zahl n generieren möchten, können Sie den Lucas-Lehmer-Test verwenden, um Mersenne-Primzahlen zu überprüfen. Eine Mersenne-Primzahl hat die Form 2 ^ p -1. Ich denke, dass der Lucas-Lehmer-Test der schnellste Algorithmus ist, der für Mersenne-Primzahlen entdeckt wurde.

Wenn Sie nicht nur den schnellsten Algorithmus, sondern auch die schnellste Hardware verwenden möchten, versuchen Sie, ihn mit Nvidia CUDA zu implementieren, schreiben Sie einen Kernel für CUDA und führen Sie ihn auf der GPU aus.

Sie können sogar etwas Geld verdienen, wenn Sie genügend Primzahlen entdecken. EFF vergibt Preise zwischen 50.000 und 250.000 US-Dollar: https://www.eff.org/awards/coop

Es gibt einen 100% igen mathematischen Test, der prüft, ob eine Zahl Peine Primzahl oder eine zusammengesetzte Zahl ist, den AKS-Primalitätstest .

Das Konzept ist einfach: PWenn bei einer gegebenen Zahl alle Koeffizienten von (x-1)^P - (x^P-1)durch teilbar sind P, Phandelt es sich um eine Primzahl, andernfalls um eine zusammengesetzte Zahl.

Zum Beispiel P = 3würde gegeben das Polynom geben:

   (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 ist die Zahl eine Primzahl.

Und Beispiel wo P = 4, was NICHT eine Primzahl ist, würde ergeben:

   (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 6nicht durch teilbar sind 4, daher ist es NICHT Primzahl.

Das Polynom (x-1)^Pwird P+1Begriffe und kann durch Kombination gefunden werden. Dieser Test wird also zur O(n)Laufzeit ausgeführt, daher weiß ich nicht, wie nützlich dies wäre, da Sie einfach ivon 0 nach iterieren pund den Rest testen können.

Ist es Ihr Problem zu entscheiden, ob eine bestimmte Zahl eine Primzahl ist? Dann brauchen Sie einen Primalitätstest (einfach). Oder benötigen Sie alle Primzahlen bis zu einer bestimmten Anzahl? In diesem Fall sind die Hauptsiebe gut (einfach, erfordern jedoch Speicher). Oder brauchen Sie die Primfaktoren einer Zahl? Dies würde eine Faktorisierung erfordern (schwierig für große Zahlen, wenn Sie wirklich die effizientesten Methoden wünschen). Wie groß sind die Zahlen, die Sie betrachten? 16 Bit? 32 Bit? größer?

Eine clevere und effiziente Möglichkeit besteht darin, Primzahlen-Tabellen vorab zu berechnen und sie mithilfe einer Codierung auf Bitebene in einer Datei zu speichern. Die Datei wird als ein langer Bitvektor betrachtet, während Bit n eine ganze Zahl n darstellt. Wenn n eine Primzahl ist, wird sein Bit auf Eins und ansonsten auf Null gesetzt. Die Suche ist sehr schnell (Sie berechnen den Byte-Offset und eine Bitmaske) und erfordert kein Laden der Datei in den Speicher.

Rabin-Miller ist ein standardmäßiger probabilistischer Primalitätstest. (Sie führen Sie es K - mal und die Eingangsnummer ist entweder auf jeden Fall zusammengesetzt, oder es ist wahrscheinlich Primzahl mit Fehlerwahrscheinlichkeit 4 ^-K . (ein paar hundert Iterationen und es wird mit ziemlicher Sicherheit sagen Sie die Wahrheit)

Es gibt eine nicht-probabilistische (deterministische) Variante von Rabin Miller .

Die Great Internet Mersenne Prime Search (GIMPS), die den Weltrekord für die größte nachgewiesene Primzahl gefunden hat (2 ^74.207.281 - 1, Stand Juni 2017), verwendet mehrere Algorithmen , aber dies sind Primzahlen in speziellen Formen. Die obige GIMPS-Seite enthält jedoch einige allgemeine deterministische Primalitätstests. Sie scheinen anzuzeigen, dass der "schnellste" Algorithmus von der Größe der zu testenden Zahl abhängt. Wenn Ihre Zahl in 64 Bit passt, sollten Sie wahrscheinlich keine Methode verwenden, die für Primzahlen mit mehreren Millionen Ziffern vorgesehen ist.

Das hängt von Ihrer Bewerbung ab. Es gibt einige Überlegungen:

• Benötigen Sie nur die Information, ob einige Zahlen Primzahlen sind, benötigen Sie alle Primzahlen bis zu einem bestimmten Grenzwert oder benötigen Sie (möglicherweise) alle Primzahlen?
• Wie groß sind die Zahlen, mit denen Sie umgehen müssen?

Die Miller-Rabin- und Analogtests sind nur schneller als ein Sieb für Zahlen über einer bestimmten Größe (ungefähr ein paar Millionen, glaube ich). Darunter ist die Verwendung einer Probedivision (wenn Sie nur wenige Zahlen haben) oder eines Siebs schneller.

Ich verwende diese Methode immer zur Berechnung der Primzahlen, die mit dem Siebalgorithmus folgen.

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);
 }

Ich werde Sie entscheiden lassen, ob es das schnellste ist oder nicht.

using System;
namespace PrimeNumbers
{

public static class Program
{
    static int primesCount = 0;


    public static void Main()
    {
        DateTime startingTime = DateTime.Now;

        RangePrime(1,1000000);   

        DateTime endingTime = DateTime.Now;

        TimeSpan span = endingTime - startingTime;

        Console.WriteLine("span = {0}", span.TotalSeconds);

    }


    public static void RangePrime(int start, int end)
    {
        for (int i = start; i != end+1; i++)
        {
            bool isPrime = IsPrime(i);
            if(isPrime)
            {
                primesCount++;
                Console.WriteLine("number = {0}", i);
            }
        }
        Console.WriteLine("primes count = {0}",primesCount);
    }



    public static bool IsPrime(int ToCheck)
    {

        if (ToCheck == 2) return true;
        if (ToCheck < 2) return false;


        if (IsOdd(ToCheck))
        {
            for (int i = 3; i <= (ToCheck / 3); i += 2)
            {
                if (ToCheck % i == 0) return false;
            }
            return true;
        }
        else return false; // even numbers(excluding 2) are composite
    }

    public static bool IsOdd(int ToCheck)
    {
        return ((ToCheck % 2 != 0) ? true : false);
    }
}
}

Auf meinem Core 2 Duo-Laptop mit einem 2,40-GHz-Prozessor dauert es ungefähr 82 Sekunden , um Primzahlen im Bereich von 1 bis 1.000.000 zu finden und zu drucken. Und es wurden 78.498 Primzahlen gefunden.

#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);
}    

Ich kenne keinen vordefinierten Algorithmus, aber ich habe meinen eigenen erstellt, der sehr schnell ist. Es kann 20-stellige Zahlen in weniger als 1 Sekunde verarbeiten. Die maximale Kapazität dieses Programms beträgt 18446744073709551615. Das Programm lautet:

#include <iostream>
#include <cmath>
#include <stdlib.h>

using namespace std;

unsigned long long int num = 0;

bool prime() {
    if (num % 2 == 0 || num == 1) {
        return false;
    }

    unsigned long int square_root = sqrt(num);
    for (unsigned long int i = 3; i <= square_root; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

int main() {
    do {
        system("cls");
        cout << "Enter number : ";
        cin >> num;

        if (prime()) {
            cout << "The number is a prime number" << endl << endl << endl << endl;
        } else {
            cout << "The number is not a prime number" << endl << endl << endl << endl;
        }
        system("pause");
    } while (1);

    return 0;
}

#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;
}

Ich weiß, dass es etwas später ist, aber dies könnte für Leute nützlich sein, die von Suchanfragen hierher kommen. Wie auch immer, hier ist etwas JavaScript, das auf der Tatsache beruht, dass nur Primfaktoren getestet werden müssen, sodass die vom Code generierten früheren Primzahlen als Testfaktoren für spätere wiederverwendet werden. Natürlich werden zuerst alle geraden und Mod 5-Werte herausgefiltert. Das Ergebnis befindet sich im Array P, und dieser Code kann 10 Millionen Primzahlen in weniger als 1,5 Sekunden auf einem i7-PC (oder 100 Millionen in etwa 20) knacken. In C umgeschrieben sollte es sehr schnell sein.

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
}

#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<<", ";

    }
}