Algoritme manakah yang tercepat untuk menemukan bilangan prima?

Manakah algoritma tercepat untuk mengetahui bilangan prima menggunakan C ++? Saya telah menggunakan algoritme saringan tetapi saya tetap menginginkannya lebih cepat!

Implementasi yang sangat cepat dari Saringan Atkin adalah primegen Dan Bernstein . Saringan ini lebih efisien daripada Saringan Eratosthenes . Halamannya memiliki beberapa informasi benchmark.

Jika harus sangat cepat, Anda dapat memasukkan daftar bilangan prima:
http://www.bigprimes.net/archive/prime/

Jika Anda hanya perlu tahu apakah angka tertentu adalah bilangan prima, ada berbagai tes prima yang terdaftar di wikipedia . Mereka mungkin merupakan metode tercepat untuk menentukan apakah angka besar adalah bilangan prima, terutama karena mereka dapat memberi tahu Anda jika angka bukanlah bilangan prima.

He, he I know I'm a pertanyaan ahli nujum menjawab pertanyaan-pertanyaan lama, tapi saya baru saja menemukan pertanyaan ini mencari di internet cara untuk menerapkan tes bilangan prima yang efisien.

Sampai sekarang, saya percaya bahwa algoritma pengujian bilangan prima tercepat adalah Strong Probable Prime (SPRP). Saya mengutip dari forum Nvidia CUDA:

Salah satu masalah ceruk yang lebih praktis dalam teori bilangan berkaitan dengan identifikasi bilangan prima. Mengingat N, bagaimana Anda bisa menentukan secara efisien apakah itu prima atau tidak? Ini bukan hanya masalah thoeretical, itu mungkin masalah nyata yang dibutuhkan dalam kode, mungkin ketika Anda perlu secara dinamis menemukan ukuran tabel hash utama dalam rentang tertentu. Jika N adalah sesuatu dengan urutan 2 ^ 30, apakah Anda benar-benar ingin melakukan 30000 tes pembagian untuk mencari faktor apa pun? Tentu saja tidak.

Solusi praktis umum untuk masalah ini adalah tes sederhana yang disebut Euler probable prime test, dan generalisasi yang lebih kuat yang disebut Strong Probable Prime (SPRP). Ini adalah tes yang untuk bilangan bulat N secara probabilistik dapat mengklasifikasikannya sebagai bilangan prima atau tidak, dan tes berulang dapat meningkatkan probabilitas kebenaran. Bagian lambat dari tes itu sendiri sebagian besar melibatkan perhitungan nilai yang mirip dengan modul A ^ (N-1) N. Siapa pun yang menerapkan varian enkripsi kunci publik RSA telah menggunakan algoritma ini. Ini berguna baik untuk bilangan bulat besar (seperti 512 bit) maupun ints normal 32 atau 64 bit.

Tes ini dapat diubah dari penolakan probabilistik menjadi bukti definitif primality dengan mengkomputasi parameter input tes tertentu yang diketahui selalu berhasil untuk rentang N. Sayangnya penemuan "tes paling terkenal" ini secara efektif adalah pencarian yang besar ( sebenarnya infinite) domain. Pada tahun 1980, daftar pertama dari tes yang berguna dibuat oleh Carl Pomerance (terkenal karena menjadi faktor RSA-129 dengan algoritma Quadratic Seive-nya.) Kemudian Jaeschke meningkatkan hasil secara signifikan pada tahun 1993. Pada tahun 2004, Zhang dan Tang meningkatkan teorinya. dan batas-batas domain pencarian. Greathouse dan Livingstone telah merilis hasil paling modern hingga sekarang di web, di http://math.crg4.com/primes.html , hasil terbaik dari domain pencarian yang sangat besar.

Lihat di sini untuk info lebih lanjut: http://primes.utm.edu/prove/prove2_3.html dan http://forums.nvidia.com/index.php?showtopic=70483

Jika Anda hanya membutuhkan cara untuk menghasilkan bilangan prima yang sangat besar dan tidak peduli untuk menghasilkan semua bilangan prima <bilangan bulat, Anda dapat menggunakan uji Lucas-Lehmer untuk memverifikasi bilangan prima Mersenne. Bilangan prima Mersenne adalah dalam bentuk 2 ^ p -1. Saya berpikir bahwa uji Lucas-Lehmer adalah algoritma tercepat yang ditemukan untuk bilangan prima Mersenne.

Dan jika Anda tidak hanya ingin menggunakan algoritma tercepat tetapi juga perangkat keras tercepat, cobalah untuk mengimplementasikannya menggunakan Nvidia CUDA, tulis kernel untuk CUDA dan jalankan di GPU.

Anda bahkan dapat memperoleh uang jika Anda menemukan bilangan prima yang cukup besar, EFF memberikan hadiah mulai dari $ 50 ribu hingga $ 250 ribu: https://www.eff.org/awards/coop

Ada tes matematika 100% yang akan memeriksa apakah suatu bilangan Pprima atau gabungan, yang disebut AKS Primality Test .

Konsepnya sederhana: diberi angka P, jika semua koefisien (x-1)^P - (x^P-1)dapat dibagi dengan P, maka Padalah bilangan prima, jika tidak maka itu adalah bilangan komposit.

Misalnya, diberikan P = 3, akan memberikan jumlahnya banyak:

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

Dan koefisien keduanya habis dibagi 3, oleh karena itu jumlahnya prima.

Dan contoh di mana P = 4, yang BUKAN bilangan prima akan menghasilkan:

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

Dan di sini kita dapat melihat bahwa koefisien 6tidak habis dibagi 4, oleh karena itu BUKAN prima.

Polinomial (x-1)^Pakan P+1terma dan dapat ditemukan menggunakan kombinasi. Jadi, tes ini akan berjalan dalam O(n)runtime, jadi saya tidak tahu seberapa berguna ini karena Anda dapat dengan mudah beralih idari 0 ke pdan menguji sisanya.

Apakah masalah Anda untuk memutuskan apakah nomor tertentu prima? Maka Anda perlu tes primality (mudah). Atau apakah Anda membutuhkan semua bilangan prima hingga nomor tertentu? Dalam hal ini saringan utama bagus (mudah, tetapi membutuhkan memori). Atau apakah Anda memerlukan faktor utama nomor? Ini akan membutuhkan faktorisasi (sulit untuk jumlah besar jika Anda benar-benar menginginkan metode yang paling efisien). Seberapa besar angka yang Anda lihat? 16 bit? 32 bit? lebih besar?

Salah satu cara cerdas dan efisien adalah dengan pra-menghitung tabel bilangan prima dan menyimpannya dalam file menggunakan pengodean bit-level. File dianggap sebagai satu vektor bit panjang sedangkan bit n mewakili integer n. Jika n adalah prima, bitnya disetel ke satu dan ke nol sebaliknya. Pencarian sangat cepat (Anda menghitung byte offset dan bit mask) dan tidak perlu memuat file dalam memori.

Rabin-Miller adalah tes primality probabilistik standar. (Anda menjalankannya K kali dan nomor input pasti komposit, atau mungkin prima dengan probabilitas kesalahan 4- ^K . (beberapa ratus iterasi dan hampir pasti mengatakan yang sebenarnya)

Ada varian non-probabilistik (deterministik) dari Rabin Miller .

The Great Internet Mersenne Prime Search (GIMPS) yang telah menemukan rekor dunia untuk perdana terbesar terbukti (2 ^74.207.281 - 1 pada Juni 2017), menggunakan beberapa algoritma , tetapi ini adalah bilangan prima dalam bentuk khusus. Namun halaman GIMPS di atas memang menyertakan beberapa tes primality deterministik umum. Mereka muncul untuk menunjukkan bahwa algoritma mana yang "tercepat" tergantung pada ukuran angka yang akan diuji. Jika nomor Anda pas di 64 bit maka Anda mungkin tidak harus menggunakan metode yang dimaksudkan untuk bekerja pada bilangan prima beberapa juta digit.

Itu tergantung pada aplikasi Anda. Ada beberapa pertimbangan:

• Apakah Anda hanya memerlukan informasi apakah beberapa bilangan prima, apakah Anda memerlukan semua bilangan prima hingga batas tertentu, atau apakah Anda memerlukan (berpotensi) semua bilangan prima?
• Seberapa besar angka yang harus Anda tangani?

Miller-Rabin dan tes analog hanya lebih cepat dari ayakan untuk angka lebih dari ukuran tertentu (sekitar beberapa juta, saya percaya). Di bawah itu, menggunakan divisi percobaan (jika Anda hanya memiliki beberapa angka) atau ayakan lebih cepat.

Saya akan membiarkan Anda memutuskan apakah ini yang tercepat atau tidak.

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

Diperlukan sekitar 82 detik untuk menemukan dan mencetak bilangan prima dalam kisaran 1 hingga 1.000.000, pada laptop Core 2 Duo saya dengan prosesor 2,40 GHz. Dan ditemukan 78.498 bilangan prima.

Saya selalu menggunakan metode ini untuk menghitung bilangan primes mengikuti dengan algoritma ayakan.

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

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

Saya tidak tahu tentang algoritma yang telah ditentukan tetapi saya membuat sendiri yang sangat cepat. Itu dapat memproses 20 digit angka dalam waktu kurang dari 1 detik. Kemampuan maksimal program ini adalah 18446744073709551615. Program ini adalah:

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

Saya tahu ini agak terlambat, tetapi ini bisa bermanfaat bagi orang yang datang ke sini dari pencarian. Bagaimanapun, inilah beberapa JavaScript yang bergantung pada fakta bahwa hanya faktor prima yang perlu diuji, sehingga bilangan prima sebelumnya yang dihasilkan oleh kode tersebut digunakan kembali sebagai faktor pengujian untuk faktor-faktor selanjutnya. Tentu saja, semua nilai genap dan mod 5 disaring terlebih dahulu. Hasilnya akan berada di array P, dan kode ini dapat menghasilkan 10 juta bilangan prima dalam waktu kurang dari 1,5 detik pada PC i7 (atau 100 juta dalam sekitar 20). Ditulis ulang dalam C itu harus sangat cepat.

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

    }
}