Quel est l'algorithme le plus rapide pour trouver des nombres premiers?

Quel est l'algorithme le plus rapide pour trouver des nombres premiers en utilisant C ++? J'ai utilisé l'algorithme de tamis mais je veux toujours qu'il soit plus rapide!

Une mise en œuvre très rapide de la Crible d'Atkin est de Dan Bernstein de primegen . Ce tamis est plus efficace que le tamis d'Eratosthène . Sa page contient des informations de référence.

Si cela doit être très rapide, vous pouvez inclure une liste de nombres premiers:
http://www.bigprimes.net/archive/prime/

Si vous avez juste à savoir si un certain nombre est un nombre premier, il existe différents tests premiers répertoriés sur wikipedia . C'est probablement la méthode la plus rapide pour déterminer si les grands nombres sont des nombres premiers, surtout parce qu'ils peuvent vous dire si un nombre n'est pas un nombre premier.

Lui, il je sais que je suis un nécromancien de question répondant à de vieilles questions, mais je viens de trouver cette question en cherchant sur le net des moyens d'implémenter des tests de nombres premiers efficaces.

Jusqu'à présent, je pense que l'algorithme de test des nombres premiers le plus rapide est Strong Probable Prime (SPRP). Je cite des forums Nvidia CUDA:

L'un des problèmes de niche les plus pratiques de la théorie des nombres concerne l'identification des nombres premiers. Étant donné N, comment déterminer efficacement s'il est premier ou non? Ce n'est pas seulement un problème théorique, il peut s'agir d'un problème réel nécessaire dans le code, peut-être lorsque vous avez besoin de trouver dynamiquement une taille de table de hachage principale dans certaines plages. Si N est quelque chose de l'ordre de 2 ^ 30, voulez-vous vraiment faire 30000 tests de division pour rechercher des facteurs? Évidemment pas.

La solution pratique courante à ce problème est un test simple appelé test d'Euler probable premier et une généralisation plus puissante appelée Strong Probable Prime (SPRP). Il s'agit d'un test qui, pour un entier N, peut le classer de manière probabiliste comme premier ou non, et des tests répétés peuvent augmenter la probabilité d'exactitude. La partie lente du test lui-même implique principalement le calcul d'une valeur similaire à A ^ (N-1) modulo N. Quiconque implémente des variantes de chiffrement à clé publique RSA a utilisé cet algorithme. C'est utile à la fois pour les entiers énormes (comme 512 bits) ainsi que pour les entiers normaux 32 ou 64 bits.

Le test peut être changé d'un rejet probabiliste en une preuve définitive de primalité en précalculant certains paramètres d'entrée de test qui sont connus pour toujours réussir pour des plages de N. Malheureusement, la découverte de ces "tests les plus connus" est effectivement une recherche d'un énorme ( en fait infini) domaine. En 1980, une première liste de tests utiles a été créée par Carl Pomerance (célèbre pour être celui qui factorise RSA-129 avec son algorithme Quadratic Seive.) Plus tard, Jaeschke a amélioré les résultats de manière significative en 1993. En 2004, Zhang et Tang ont amélioré la théorie. et les limites du domaine de recherche. Greathouse et Livingstone ont publié les résultats les plus modernes jusqu'à présent sur le Web, à l' adresse http://math.crg4.com/primes.html , les meilleurs résultats d'un vaste domaine de recherche.

Voir ici pour plus d'informations: http://primes.utm.edu/prove/prove2_3.html et http://forums.nvidia.com/index.php?showtopic=70483

Si vous avez juste besoin d'un moyen de générer de très grands nombres premiers et que vous ne vous souciez pas de générer tous les nombres premiers <un entier n, vous pouvez utiliser le test de Lucas-Lehmer pour vérifier les nombres premiers de Mersenne. Un nombre premier de Mersenne se présente sous la forme 2 ^ p -1. Je pense que le test de Lucas-Lehmer est l'algorithme le plus rapide découvert pour les nombres premiers de Mersenne.

Et si vous voulez non seulement utiliser l'algorithme le plus rapide, mais aussi le matériel le plus rapide, essayez de l'implémenter à l'aide de Nvidia CUDA, écrivez un noyau pour CUDA et exécutez-le sur GPU.

Vous pouvez même gagner de l'argent si vous découvrez des nombres premiers suffisamment grands, l'EFF donne des prix allant de 50K $ à 250K $: https://www.eff.org/awards/coop

Il existe un test mathématique à 100% qui vérifie si un nombre Pest premier ou composé, appelé AKS Primality Test .

Le concept est simple: étant donné un nombre P, si tous les coefficients de (x-1)^P - (x^P-1)sont divisibles par P, alors Pest un nombre premier, sinon c'est un nombre composé.

Par exemple, donné P = 3, donnerait le polynôme:

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

Et les coefficients sont tous deux divisibles par 3, donc le nombre est premier.

Et par exemple, où P = 4, ce qui n'est PAS un nombre premier, produirait:

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

Et ici, nous pouvons voir que les coefficients 6ne sont pas divisibles par 4, donc ce n'est PAS premier.

Le polynôme se (x-1)^Pterminera P+1et peut être trouvé en utilisant une combinaison. Donc, ce test fonctionnera au O(n)moment de l' exécution, donc je ne sais pas à quel point cela serait utile puisque vous pouvez simplement parcourir ide 0 à pet tester le reste.

Votre problème est-il de décider si un nombre particulier est premier? Ensuite, vous avez besoin d'un test de primalité (facile). Ou avez-vous besoin de tous les nombres premiers jusqu'à un nombre donné? Dans ce cas, les tamis primaires sont bons (faciles, mais nécessitent de la mémoire). Ou avez-vous besoin des facteurs premiers d'un nombre? Cela nécessiterait une factorisation (difficile pour les grands nombres si vous voulez vraiment les méthodes les plus efficaces). Quelle est la taille des chiffres que vous regardez? 16 bits? 32 bits? plus gros?

Un moyen intelligent et efficace est de pré-calculer les tables de nombres premiers et de les conserver dans un fichier en utilisant un encodage au niveau du bit. Le fichier est considéré comme un vecteur de bits longs tandis que le bit n représente l'entier n. Si n est premier, son bit est mis à un et à zéro dans le cas contraire. La recherche est très rapide (vous calculez le décalage d'octet et un masque de bits) et ne nécessite pas le chargement du fichier en mémoire.

Rabin-Miller est un test de primalité probabiliste standard. (vous l'exécutez K fois et le nombre d'entrée est soit définitivement composite, soit il est probablement premier avec une probabilité d'erreur 4 ^-K . (quelques centaines d'itérations et cela vous dit presque certainement la vérité)

Il existe une variante non probabiliste (déterministe) de Rabin Miller .

Le Great Internet Mersenne Prime Search (GIMPS), qui a trouvé le record mondial du plus grand nombre de nombres premiers prouvés (2 ^74207281 - 1 en juin 2017), utilise plusieurs algorithmes , mais ce sont des nombres premiers sous des formes spéciales. Cependant, la page GIMPS ci-dessus inclut des tests de primalité déterministes généraux. Ils semblent indiquer que quel algorithme est "le plus rapide" dépend de la taille du nombre à tester. Si votre nombre tient en 64 bits, vous ne devriez probablement pas utiliser une méthode destinée à travailler sur des nombres premiers de plusieurs millions de chiffres.

Cela dépend de votre application. Il y a quelques considérations:

• Avez-vous simplement besoin d'informations pour savoir si quelques nombres sont premiers, avez-vous besoin de tous les nombres premiers jusqu'à une certaine limite, ou avez-vous besoin (potentiellement) de tous les nombres premiers?
• Quelle est la taille des chiffres avec lesquels vous devez faire face?

Les tests Miller-Rabin et analogiques ne sont plus rapides qu'un tamis que pour des nombres supérieurs à une certaine taille (quelque part autour de quelques millions, je crois). En dessous, utiliser une division d'essai (si vous n'avez que quelques chiffres) ou un tamis est plus rapide.

Je vous laisse décider si c'est le plus rapide ou non.

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

Il faut environ 82 secondes pour trouver et imprimer des nombres premiers dans une plage de 1 à 1 000 000, sur mon ordinateur portable Core 2 Duo avec un processeur 2,40 GHz. Et il a trouvé 78 498 nombres premiers.

J'utilise toujours cette méthode pour calculer les nombres premiers suivants avec l'algorithme de tamisage.

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

Je ne connais aucun algorithme prédéfini mais j'ai créé le mien qui est très rapide. Il peut traiter des nombres de 20 chiffres en moins de 1 seconde. La capacité maximale de ce programme est 18446744073709551615. Le programme est:

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

Je sais que c'est un peu plus tard, mais cela pourrait être utile aux personnes qui arrivent ici à la suite de recherches. Quoi qu'il en soit, voici un code JavaScript qui repose sur le fait que seuls les facteurs premiers doivent être testés, de sorte que les premiers nombres premiers générés par le code sont réutilisés comme facteurs de test pour les plus récents. Bien sûr, toutes les valeurs paires et mod 5 sont filtrées en premier. Le résultat sera dans le tableau P, et ce code peut écraser 10 millions de nombres premiers en moins de 1,5 seconde sur un PC i7 (ou 100 millions dans environ 20). Réécrit en C ça devrait être très rapide.

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

    }
}