webentwicklung-frage-antwort-db.com.de

Welches ist der schnellste Algorithmus, um Primzahlen zu finden?

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

169
kasperasky

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

71
Greg Hewgill

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

Wenn Sie nur wissen müssen, ob eine bestimmte Zahl eine Primzahl ist, gibt es verschiedene Primestests, die auf Wikipedia aufgelistet sind. Sie sind wahrscheinlich die schnellste Methode, um zu bestimmen, ob große Zahlen Primzahlen sind, vor allem, weil sie Ihnen sagen können, ob eine Zahl keine Primzahl ist.

26
Georg Schölly

Er, er weiß, ich bin ein Neokromant, der alte Fragen beantwortet, aber ich habe gerade diese Frage auf der Suche nach Möglichkeiten gefunden, effiziente Primzahlentests zu implementieren.

Bisher glaube ich, dass der schnellste Algorithmus zum Testen der Primzahl Strong Probable Prime (SPRP) ist. Ich zitiere aus Nvidia CUDA-Foren: 

Eines der praktischeren Nischenprobleme in der Zahlentheorie muss es tun. mit Identifizierung der Primzahlen. Wie können Sie bei gegebenem N effizient bestimmen, ob es Primzahl ist oder nicht? Dies ist nicht nur ein theoretisches Problem, es kann ein echtes im Code benötigt werden, vielleicht wenn Finden Sie dynamisch eine Prim-Hash-Tabellengröße innerhalb bestimmter Bereiche. Wenn N ist etwas in der Größenordnung von 2 ^ 30, möchten Sie wirklich 30000 Divisionstests, um nach Faktoren zu suchen? Offensichtlich nicht.

Die übliche praktische Lösung für dieses Problem ist ein einfacher Test namens ein wahrscheinlicher Euler-Test und eine stärkere Verallgemeinerung nannte einen starken wahrscheinlichen Prime (SPRP). Dies ist ein Test für einen Ganzzahl N kann es probabilistisch als Primzahl oder nicht klassifizieren, und Wiederholte Tests können die Wahrscheinlichkeit der Korrektheit erhöhen. Der langsame Teil des Tests selbst besteht meistens aus der Berechnung eines Wertes ähnlich wie A ^ (N-1) modulo N. Jeder, der die RSA-Verschlüsselung mit öffentlichen Schlüsseln implementiert Varianten hat diesen Algorithmus verwendet. Dies ist sowohl für große Ganzzahlen als auch nützlich. (wie 512 Bit) sowie normale 32- oder 64-Bit-Ints.

Der Test kann von einer probabilistischen Ablehnung in eine .__ geändert werden. endgültiger Nachweis der Ursprünglichkeit durch Vorberechnung bestimmter Testeingaben Parameter, 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 einer riesigen (tatsächlich unendlich vielen) Domäne. 1980 wurde eine erste Liste von nützliche Tests wurden von Carl Pomerance (bekannt als derjenige, der RSA-129 mit seinem quadratischen Seive-Algorithmus in Betracht zog) erstellt. Später Jaeschke Die Ergebnisse wurden 1993 erheblich verbessert. 2004 haben Zhang und Tang Theorie und Grenzen der Suchdomäne verbessert. Großhaus und Livingstone hat bisher die modernsten Ergebnisse auf der .__ veröffentlicht. web, unter http://math.crg4.com/primes.html , die besten Ergebnisse eines großen Domain suchen.

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 die Mersenne-Primzahlen zu überprüfen. Eine Mersenne-Primzahl hat die Form von 2 ^ p -1. Ich denke, dass der Lucas-Lehmer-Test der schnellste Algorithmus ist, der für Mersenne-Primzahlen entdeckt wurde.

Und 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 GPU aus.

Sie können sogar etwas Geld verdienen, wenn Sie ausreichend große Primzahlen entdecken. Die EFF gibt Preise von 50.000 bis 250.000 Dollar: https://www.eff.org/awards/coop

25
Mack

Es gibt einen 100% mathematischen Test, der überprüft, ob eine Zahl P eine Primzahl oder eine zusammengesetzte Zahl ist, die als AKS Primality Test bezeichnet wird. 

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

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

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

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

Beispiel: P = 4, das 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 6 nicht durch 4 teilbar sind, daher nicht prim.

Das Polynom (x-1)^P wird P+1 und kann durch Kombination gefunden werden. Daher wird dieser Test in O(n) runtime ausgeführt, daher weiß ich nicht, wie nützlich dies ist, da Sie einfach i von 0 nach p durchlaufen und den Rest testen können. 

14
Kousha

Ist es Ihr Problem zu entscheiden, ob eine bestimmte Zahl eine Primzahl ist? Dann brauchen Sie einen Primitivtest (easy). Oder benötigen Sie alle Primzahlen bis zu einer bestimmten Anzahl? In diesem Fall sind Grundsiebe gut (einfach, benötigen aber Speicher). Oder brauchen Sie die Primfaktoren einer Zahl? Dies würde eine Faktorisierung erfordern (bei großen Zahlen schwierig, wenn Sie wirklich die effizientesten Methoden wünschen). Wie groß sind die Zahlen, die Sie betrachten? 16 Bits? 32 Bits? größer?

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

5

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

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

Der Miller-Rabin-Test und die analogen Tests sind nur schneller als ein Sieb für Zahlen mit einer bestimmten Größe (irgendwo um einige Millionen, glaube ich). Darunter ist die Verwendung einer Probedivision (wenn Sie nur ein paar Zahlen haben) oder ein Sieb schneller.

2
Svante

Rabin-Miller ist ein standardmäßiger Wahrscheinlichkeitstest. (Sie führen es K-mal durch und die Eingabezahl ist entweder definitiv zusammengesetzt, oder es wird wahrscheinlich mit der Wahrscheinlichkeit des Fehlers 4 eine Primzahl angegeben-K. (ein paar hundert Iterationen und es sagt Ihnen fast sicher die Wahrheit)

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

Die Great Internet Mersenne Prime Search (GIMPS) hat den Weltrekord für die größte nachgewiesene Primzahl gefunden (274,207,281 - 1 Stand Juni 2017), verwendet mehrere Algorithmen , aber dies sind Primzahlen in speziellen Formen. Die GIMPS-Seite oben enthält jedoch einige allgemeine deterministische Ursprünglichkeitstests. Sie scheinen darauf hinzuweisen, dass der Algorithmus "am schnellsten" von der Größe der zu testenden Zahl abhängt. Wenn Ihre Anzahl in 64 Bits passt, sollten Sie wahrscheinlich keine Methode verwenden, die für Primzahlen mit mehreren Millionen Stellen geeignet ist.

2
Jason S

Ich lasse Sie entscheiden, 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);
    }
}
}

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

1
Tayyab Mazhar