Który algorytm jest najszybszy do znalezienia liczb pierwszych?

Jaki jest najszybszy algorytm do znajdowania liczb pierwszych za pomocą C ++? Użyłem algorytmu sita, ale nadal chcę, aby był szybszy!

Bardzo szybką implementacją Sita Atkina jest primegen Dana Bernsteina . To sito jest bardziej wydajne niż sito Eratostenesa . Jego strona zawiera informacje porównawcze.

Jeśli ma być naprawdę szybki, możesz dołączyć listę liczb pierwszych:
http://www.bigprimes.net/archive/prime/

Jeśli musisz tylko wiedzieć, czy określona liczba jest liczbą pierwszą, na Wikipedii można znaleźć różne testy podstawowe . Są to prawdopodobnie najszybsze metody ustalenia, czy duże liczby są liczbami pierwszymi, szczególnie dlatego, że mogą powiedzieć, czy liczba nie jest liczbą pierwszą.

On, wiem, że jestem nekromantą, który odpowiada na stare pytania, ale właśnie znalazłem to pytanie, szukając w sieci sposobów na wdrożenie skutecznych testów liczb pierwszych.

Do tej pory uważam, że najszybszym algorytmem testowania liczb pierwszych jest Strong Probable Prime (SPRP). Cytuję z forów Nvidia CUDA:

Jeden z bardziej praktycznych problemów niszowych w teorii liczb dotyczy identyfikacji liczb pierwszych. Biorąc pod uwagę N, jak możesz skutecznie ustalić, czy jest to liczba pierwsza, czy nie? To nie jest tylko problem thoeretyczny, może być prawdziwy, potrzebny w kodzie, być może, gdy trzeba dynamicznie znaleźć główny rozmiar tablicy skrótów w określonych zakresach. Jeśli N jest rzędu 2 ^ 30, to czy naprawdę chcesz przeprowadzić testy podziału 30000, aby wyszukać jakieś czynniki? Oczywiście, że nie.

Powszechnym praktycznym rozwiązaniem tego problemu jest prosty test zwany prawdopodobnym testem podstawowym Eulera i bardziej wydajne uogólnienie o nazwie Strong Probable Prime (SPRP). Jest to test, który dla liczby całkowitej N może probabilistycznie sklasyfikować ją jako liczbę pierwszą lub nie, a powtarzane testy mogą zwiększyć prawdopodobieństwo poprawności. Powolna część samego testu polega głównie na obliczeniu wartości podobnej do modułu A ^ (N-1) N. Każdy, kto implementuje warianty szyfrowania klucza publicznego RSA, zastosował ten algorytm. Jest to przydatne zarówno dla dużych liczb całkowitych (jak 512 bitów), jak i normalnych 32 lub 64-bitowych liczb całkowitych.

Test można zmienić z probabilistycznego odrzucenia na ostateczny dowód pierwotności, wstępnie obliczając pewne parametry wejściowe testu, o których wiadomo, że zawsze odnoszą sukcesy dla przedziałów N. Niestety odkrycie tych „najbardziej znanych testów” jest w rzeczywistości poszukiwaniem ogromnego ( w rzeczywistości nieskończona) domena. W 1980 r. Carl Pomerance stworzył pierwszą listę przydatnych testów (znaną z tego, że bierze pod uwagę czynnik RSA-129 ze swoim algorytmem Quadratic Seive). Później Jaeschke znacznie poprawił wyniki w 1993 r. W 2004 r. Zhang i Tang poprawili teorię i ograniczenia domeny wyszukiwania. Greathouse i Livingstone opublikowały do ​​tej pory najnowocześniejsze wyniki w Internecie pod adresem http://math.crg4.com/primes.html , najlepsze wyniki ogromnej domeny wyszukiwania.

Zobacz tutaj, aby uzyskać więcej informacji: http://primes.utm.edu/prove/prove2_3.html i http://forums.nvidia.com/index.php?showtopic=70483

Jeśli potrzebujesz tylko sposobu generowania bardzo dużych liczb pierwszych i nie chcesz generować wszystkich liczb pierwszych <liczba całkowita n, możesz użyć testu Lucas-Lehmera, aby zweryfikować liczby pierwsze Mersenne. Liczba pierwsza Mersenne ma postać 2 ^ p -1. Myślę, że test Lucas-Lehmera jest najszybszym algorytmem odkrytym dla liczb pierwszych Mersenne.

A jeśli chcesz użyć nie tylko najszybszego algorytmu, ale także najszybszego sprzętu, spróbuj go zaimplementować za pomocą Nvidia CUDA, napisz jądro dla CUDA i uruchom je na GPU.

Możesz nawet zarobić trochę pieniędzy, jeśli odkryjesz wystarczająco duże liczby pierwsze, EFF daje nagrody od 50 000 $ do 250 000 $: https://www.eff.org/awards/coop

Istnieje 100% test matematyczny, który sprawdzi, czy liczba Pjest liczbą pierwszą czy złożoną, zwany testem pierwszeństwa AKS .

Koncepcja jest prosta: biorąc pod uwagę liczbę P, jeśli wszystkie współczynniki (x-1)^P - (x^P-1)są podzielne P, to Pjest liczbą pierwszą, w przeciwnym razie jest liczbą złożoną.

Na przykład, podany P = 3, dałby wielomian:

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

A oba współczynniki są podzielne 3, dlatego liczba jest liczbą pierwszą.

I przykład gdzie P = 4, co NIE jest liczbą pierwszą, dałoby:

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

I tutaj widzimy, że współczynniki 6nie są podzielne 4, dlatego NIE jest to liczba pierwsza.

Wielomian (x-1)^Pbędzie P+1terminami i można go znaleźć za pomocą kombinacji. Tak więc ten test będzie działał w O(n)środowisku uruchomieniowym , więc nie wiem, jak przydatne byłoby to, ponieważ możesz po prostu iterować iod 0 do pi testować resztę.

Czy masz problem z ustaleniem, czy określona liczba jest liczbą pierwszą? Następnie potrzebujesz testu pierwszeństwa (łatwy). A może potrzebujesz wszystkich liczb pierwszych do podanej liczby? W takim przypadku sita główne są dobre (łatwe, ale wymagają pamięci). A może potrzebujesz liczb pierwszych? Wymagałoby to faktoryzacji (trudne dla dużych liczb, jeśli naprawdę chcesz najbardziej wydajnych metod). Jak duże są liczby, na które patrzysz? 16 bitów? 32 bity? większy?

Jednym sprytnym i wydajnym sposobem jest wstępne obliczenie tabel liczb pierwszych i przechowywanie ich w pliku przy użyciu kodowania na poziomie bitów. Plik jest uważany za jeden długi wektor bitowy, podczas gdy bit n reprezentuje liczbę całkowitą n. Jeśli n jest liczbą pierwszą, jej bit jest ustawiony na jeden, a w przeciwnym razie na zero. Wyszukiwanie jest bardzo szybkie (obliczasz przesunięcie bajtu i maskę bitową) i nie wymaga ładowania pliku do pamięci.

Rabin-Miller to standardowy probabilistyczny test pierwszeństwa. (uruchamiasz go K razy, a liczba wejściowa jest albo zdecydowanie złożona, albo prawdopodobnie jest liczbą pierwszą z prawdopodobieństwem błędu 4- ^K . (kilkaset iteracji i prawie na pewno mówi prawdę)

Istnieje wariant probabilistyczny (deterministyczny) Rabina Millera .

Great Internet Mersenne Prime Search (GIMPS), który stwierdził, rekord świata o największym sprawdzonej sile (2 ^74,207,281 - 1 z czerwca 2017), wykorzystuje wiele algorytmów , ale są to liczby pierwsze w specjalnych formach. Jednak strona GIMPS powyżej zawiera pewne ogólne deterministyczne testy pierwotności. Wydaje się, że wskazują, że który algorytm jest „najszybszy”, zależy od wielkości liczby do przetestowania. Jeśli twoja liczba mieści się w 64 bitach, prawdopodobnie nie powinieneś używać metody przeznaczonej do pracy na liczbach pierwszych kilku milionów cyfr.

To zależy od twojej aplikacji. Istnieje kilka uwag:

• Czy potrzebujesz tylko informacji, czy kilka liczb pierwszych jest liczbą pierwszą, czy potrzebujesz wszystkich liczb pierwszych do określonego limitu, czy potrzebujesz (potencjalnie) wszystkich liczb pierwszych?
• Jak duże są liczby, z którymi masz do czynienia?

Testy Millera-Rabina i testy analogowe są szybsze niż sito dla liczb powyżej pewnego rozmiaru (wydaje mi się, że około kilku milionów). Poniżej, korzystanie z podziału próbnego (jeśli masz tylko kilka liczb) lub sita jest szybsze.

Zawsze używam tej metody do obliczania liczb pierwszych po algorytmie sitowym.

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

Pozwolę ci zdecydować, czy jest to najszybszy czy nie.

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

Znalezienie i wydrukowanie liczb pierwszych w zakresie od 1 do 1 000 000 zajmuje około 82 sekund na moim laptopie Core 2 Duo z procesorem 2,40 GHz. I znaleziono 78 498 liczb pierwszych.

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

Nie znam żadnego predefiniowanego algorytmu, ale stworzyłem własny, który jest bardzo szybki. Może przetwarzać 20 cyfr w mniej niż 1 sekundę. Maksymalna zdolność tego programu to 18446744073709551615. Program to:

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

Wiem, że to trochę później, ale może to być przydatne dla osób przybywających tutaj z wyszukiwań. Tak czy inaczej, oto niektóre JavaScript, który opiera się na fakcie, że tylko czynniki pierwsze muszą zostać przetestowane, więc wcześniejsze liczby pierwsze wygenerowane przez kod są ponownie wykorzystywane jako czynniki testowe dla późniejszych. Oczywiście wszystkie wartości parzyste i mod 5 są najpierw filtrowane. Wynik będzie w tablicy P, a ten kod może rozbić 10 milionów liczb pierwszych w mniej niż 1,5 sekundy na komputerze i7 PC (lub 100 milionów w około 20). Przepisany w C powinien być bardzo szybki.

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

    }
}