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 C ++? J’ai utilisé l’algorithme de tamis mais je veux toujours qu’il soit plus rapide!

Une mise en œuvre très rapide du tamis d’Atkin est la primegen de Dan Bernstein. Ce tamis est plus efficace que le tamis d’Eratosthenes . 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 devez juste savoir si un certain nombre est un nombre premier, divers tests principaux sont listés sur Wikipédia . Ils sont 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, je sais que je suis un nécromancien qui répond à d’anciennes questions, mais je viens de trouver cette question en cherchant sur le net des façons de mettre en œuvre des tests efficaces de nombres premiers.

Jusqu’à présent, je crois que l’algorithme de test des nombres premiers le plus rapide est le Fort Probable Premier (SPRP). Je cite des forums de Nvidia CUDA:

L’un des problèmes de niche les plus pratiques de la théorie des nombres concerne l’identification des nombres premiers. Etant donné N, comment pouvez-vous déterminer efficacement si c’est primordial ou non? Ce n’est pas juste un problème théorique, il peut s’agir d’un problème réel nécessaire dans le code, peut-être lorsque vous devez trouver dynamicment 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 de prime probable d’Euler, et une généralisation plus puissante appelée un fort probable fort (SPRP). Ceci est un test qui, pour un entier N, peut le classer de façon probabiliste comme premier ou non, et des tests répétés peuvent augmenter la probabilité de correction. La partie lente du test lui-même implique principalement le calcul d’une valeur similaire à A ^ (N-1) modulo N. Toute personne implémentant des variantes de chiffrement à clé publique RSA a utilisé cet algorithme. C’est utile aussi bien pour les entiers énormes (comme 512 bits) que pour les entiers normaux de 32 ou 64 bits.

On peut changer le test d’un rejet probabiliste en une preuve définitive de primalité en précalculant certains parameters d’entrée de test connus pour réussir toujours dans des gammes de N. Malheureusement, la découverte de ces “tests les plus connus” est effectivement une recherche é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 le facteur 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 limites du domaine de recherche. Greathouse et Livingstone ont publié les résultats les plus modernes 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 gros nombres premiers et de ne pas générer tous les nombres premiers

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 en utilisant Nvidia CUDA, écrivez un kernel pour CUDA et exécutez-le sur le GPU.

Vous pouvez même gagner un peu d’argent si vous découvrez des nombres premiers suffisamment importants. Le FEP accorde des prix allant de 50 000 à 250 000 dollars: https://www.eff.org/awards/coop

Un test mathématique à 100% vérifie si un nombre P est premier ou non, appelé test de primauté AKS .

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

Par exemple, étant donné que 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 exemple où P = 4 , qui n’est pas un nombre premier donnerait:

  (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 6 ne sont pas divisibles par 4 , par conséquent, il n’est PAS premier.

Le polynôme (x-1)^P sera P+1 termes et peut être trouvé en utilisant la combinaison. Donc, ce test sera exécuté dans O(n) runtime, donc je ne sais pas à quel point cela serait utile puisque vous pouvez simplement parcourir i de 0 à p et tester le rest.

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 principaux 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?

Une façon intelligente et efficace consiste à pré-calculer des tables de nombres premiers et à les conserver dans un fichier en utilisant un codage au niveau du bit. Le fichier est considéré comme un vecteur de long bit alors que le bit n représente un entier n. Si n est premier, son bit est mis à un et à zéro sinon. La recherche est très rapide (vous calculez le décalage d’octet et un masque de bits) et ne nécessite pas de charger le fichier en mémoire.

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 numéros à traiter?

Les tests Miller-Rabin et analogiques ne sont que plus rapides qu’un tamis pour des nombres dépassant 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.

Rabin-Miller est un test de primalité probabiliste standard. (vous l’exécutez K fois et le nombre en entrée est soit définitivement composite, soit probablement premier avec la probabilité d’erreur 4- K . (quelques centaines d’itérations et c’est 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 facteurs premiers prouvés (2 74 207 281 – 1 en juin 2017), utilise plusieurs algorithmes , mais ceux-ci sont des nombres premiers dans des formes spéciales. Cependant, la page GIMPS ci-dessus inclut des tests de primalité déterministes généraux. Ils semblent indiquer que l’algorithme le plus “rapide” dépend de la taille du nombre à tester. Si votre numéro correspond à 64 bits, vous ne devriez probablement pas utiliser une méthode destinée à fonctionner sur des nombres premiers de plusieurs millions de chiffres.

Je vais vous laisser décider si c’est le plus rapide ou pas.

 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 compris entre 1 et 1 000 000, sur mon ordinateur portable Core 2 Duo équipé d’un processeur de 2,40 GHz. Et il a trouvé 78 498 nombres premiers.

J’utilise toujours cette méthode pour calculer les nombres premiers avec l’algorithme de tamis.

 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 main() { long long unsigned x,y,b,z,e,r,c; scanf("%llu",&x); if(x<2)return 0; scanf("%llu",&y); if(y0)z=3; } if(e==0) { printf("|%llu",z); r+=1; } } printf("|\n%llu outputs...\n",r); scanf("%llu",&r); } 
 #include  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 pour les personnes arrivant des recherches. Quoi qu’il en soit, voici un code JavaScript qui repose sur le fait que seuls les facteurs premiers doivent être testés. Les premiers nombres premiers générés par le code sont donc réutilisés comme facteurs de test pour les versions ultérieures. 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 traiter 10 millions de nombres premiers en moins de 1,5 seconde sur un PC i7 (ou 100 millions sur environ 20). Réécrit en C, il 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 using namespace std; void main() { int num,i,j,prime; cout<<"Enter the upper limit :"; cin>>num; cout<<"Prime numbers till "<