Welcher ist der schnellste Algorithmus zur Auffindung von Primzahlen?

Question

Welcher ist der schnellste Algorithmus, um Primzahlen mit C++ zu finden? Ich habe das Siebverfahren verwendet, aber ich möchte immer noch, dass es schneller wird!

Answer 1

Rabin-Miller ist ein Standard-Probabilistik-Primzahlentest. (Sie führen ihn K-mal aus und die Eingangsnummer ist entweder definitiv zusammengesetzt oder sie ist wahrscheinlich prim mit einer Fehlerwahrscheinlichkeit von 4-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), die den Weltrekord für die größte nachgewiesene Primzahl gefunden hat (274,207,281 - 1 ab Juni 2017), verwendet mehrere Algorithmen, aber dies sind Primzahlen in speziellen Formen. Die GIMPS-Seite oben enthält jedoch einige allgemeine deterministische Primzahlentests. Sie scheinen darauf hinzuweisen, dass davon abhängt, welcher Algorithmus "schnell" ist, abhängig von der Größe der zu testenden Zahl. Wenn Ihre Zahl in 64 Bits passt, sollten Sie wahrscheinlich keine Methode verwenden, die für Primzahlen mit mehreren Millionen Ziffern gedacht ist.

Answer 2

Dies ist eine Implementierung des Sieb des Eratosthenes in Python, mit der ich herumgespielt habe.

def eratosthenes(maximum: int) -> list[int | None]:
    """
    Finde alle Primzahlen zwischen 2 und `maximum`.

    Args:
        maximum: Die maximale Zahl, die überprüft werden soll.

    Returns:
        Eine Liste von Primzahlen zwischen 2 und `maximum`.
    """

    if maximum < 2:
        return []

    # Gerade Zahlen standardmäßig verwerfen.
    sequence = dict.fromkeys(range(3, maximum+1, 2), True)

    for num, is_prime in sequence.items():
        # Bereits gefiltert, überspringen wir es.
        if not is_prime:
            continue

        # Vermeide das Markieren der gleichen Zahl zweimal.
        for num2 in range(num ** 2, maximum+1, num):
            # Hier könnte `num2` eine gerade Zahl enthalten - überspringe sie.
            if num2 in sequence:
                sequence[num2] = False

    # Füge 2 wieder als Primzahl hinzu und filtere die zusammengesetzten Zahlen heraus.
    return [2] + [num for num, is_prime in sequence.items() if is_prime]

Der Code scheint auf einem einfachen Samsung Galaxy A40 ungefähr 16s für 10000000 Zahlen zu benötigen.

Vorschläge sind willkommen!

Answer 3

Es kommt auf Ihre Anwendung an. Es gibt einige Überlegungen:

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

Die Miller-Rabin und analoge Tests sind nur schneller als ein Sieb für Zahlen über einer bestimmten Größe (irgendwo um ein paar Millionen, glaube ich). Darunter ist eine Testdivision (wenn Sie nur ein paar Zahlen haben) oder ein Sieb schneller.

Answer 4

Ich habe diese Lösung ziemlich schnell gefunden, aber sie hat Konsequenzen. Dies wird Fermats kleiner Satz genannt. Wenn wir eine beliebige Zahl p nehmen und diese in (1^p)-1 oder (2^p)-2...(n^p)-n usw. einsetzen und die Zahl, die wir erhalten, durch p teilbar ist, dann handelt es sich um eine Primzahl. Bezüglich der Konsequenzen ist es keine 100%ige richtige Lösung. Es gibt einige Zahlen wie 341 (nicht prim), die den Test mit (2^341)-2 bestehen werden, aber bei (3^341)-3 durchfallen, daher werden sie als zusammengesetzte Zahlen bezeichnet. Wir können zwei oder mehr Überprüfungen durchführen, um sicherzustellen, dass sie alle bestehen. Es gibt noch eine Art von Zahlen, die nicht prim sind, aber auch alle Testfälle bestehen: (561, 1729 Ramanujan-Taxi-Nr. etc.)

Das Gute: Mit (2^p)-2 fallen in den ersten 25 Milliarden Zahlen nur 2183 durch diesen Fall.

#include 
#include 
using namespace std;

int isPrime(int p)
{
    int tc = pow(2, p) - 2;
    if (tc % p == 0)
    {
        cout << p << " ist prim ";
    }
    else
    {
        cout << p << " ist nicht prim";
    }
    return 0;
}

int main()
{
    int p;
    cin >> p;
    isPrime(p);
    return 0;
}

Answer 5

Ich lasse dich entscheiden, ob es das schnellste ist oder nicht.

using System;
namespace Primzahlen
{

public static class Programm
{
    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 2,40 GHz Prozessor zu finden und auszugeben. Es wurden 78.498 Primzahlen gefunden.