Quel est l'algorithme le plus rapide pour trouver des nombres premiers en utilisant C++ ? J'ai utilisé l'algorithme de Sieve mais je voudrais qu'il soit plus rapide !
Une mise en œuvre très rapide de la Tamis d'Atkin est celui de Dan Bernstein primegen . Ce tamis est plus efficace que le Le tamis d'Eratosthène . Sa page contient des informations de référence.
En fait, je ne pense pas que primegen soit le plus rapide, ou même le deuxième plus rapide ; yafu et primesieve sont tous deux plus rapides en général, je pense, et certainement au-dessus de 2^32. Les deux sont des tamis (modifiés) d'Eratosthenes plutôt que le tamis d'Atkin-Bernstein.
Primesieve Le crible d'Eratosthène (SoE) est l'algorithme le plus rapide possible et sera toujours plus rapide que n'importe quelle implémentation du crible d'Atkin SoA, y compris celle de Bernstein comme indiqué dans cette réponse, car primesieve réduit le nombre d'opérations par rapport à SoA : Pour la plage de nombres de 32 bits (2^32 - 1), primesieve effectue environ 1,2 milliard de culls alors que SoA effectue un total d'environ 1,4 milliard d'opérations combinées de basculement et de carré libre, les deux opérations étant à peu près de la même complexité et pouvant être optimisées à peu près de la même manière.
Continué : Bernstein n'a comparé le SoE qu'en utilisant la même factorisation effective de la roue que pour le SoA, à savoir une roue 2;3;5, dont l'utilisation entraîne environ 1,83 milliard de culls sur la plage de nombres de 32 bits ; cela rend le SoA environ 30 % plus rapide. en comparant cette version restreinte de SoE pour d'autres optimisations équivalentes. Cependant, l'algorithme primesieve utilise une roue 2;3;5;7 en combinaison avec une pré-réfraction de segment de roue 2;3;5;7;11;13;17 pour réduire le nombre d'opérations à environ 1,2 milliard et s'exécuter environ 16,7 % plus rapidement que SoA avec des optimisations de boucle d'opération équivalentes.
S'il doit être vraiment rapide, vous pouvez inclure une liste de primes :
http://www.bigprimes.net/archive/prime/
Si vous voulez juste savoir si un certain nombre est un nombre premier, il y a plusieurs façons de le faire. les principaux tests répertoriés sur wikipedia . Ils sont probablement la méthode la plus rapide pour déterminer si de grands nombres sont des nombres premiers, notamment parce qu'ils peuvent vous dire si un nombre est no une prime.
Une liste de tous les nombres premiers ? Je pense que vous voulez dire une liste des quelques premiers nombres premiers... :)
Je sais que je suis un nécromancien qui répond à de vieilles questions, mais je viens de trouver cette question en cherchant sur le net des moyens de mettre en œuvre des tests efficaces sur les nombres premiers.
Jusqu'à présent, je pense que l'algorithme de test de nombres premiers le plus rapide est le Strong Probable Prime (SPRP). Je cite les forums Nvidia CUDA :
L'un des problèmes de niche les plus pratiques en théorie des nombres concerne l'identification des nombres premiers. Étant donné N, comment pouvez-vous efficacement déterminer efficacement s'il est premier ou non ? Il ne s'agit pas seulement d'un problème théorique. Il ne s'agit pas seulement d'un problème théorique, il peut s'agir d'un problème réel dont on a besoin dans le code, peut-être lorsqu'on doit trouver dynamiquement une taille de table de hachage première dans certaines limites. Si N est de l'ordre de 2^30, voulez-vous vraiment faire 30000 tests de division pour rechercher des facteurs ? tests de division pour rechercher des facteurs ? Il est évident que non.
La solution pratique courante à ce problème est un test simple appelé un test de prime probable d'Euler, et une généralisation plus puissante appelée test de la prime probable forte (SPRP). Il s'agit d'un test qui, pour un nombre 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 consiste principalement à calculer une valeur similaire à A^(N-1) modulo N. Toute personne mettant en œuvre le chiffrement à clé publique RSA a utilisé cet algorithme. Il est utile à la fois pour les grands nombres entiers (comme 512 bits) que pour les entiers normaux de 32 ou 64 bits.
Le test peut être transformé d'un rejet probabiliste en une preuve définitive de primalité en calculant à l'avance certains paramètres d'entrée du test qui sont connus pour toujours réussir pour des plages de N. Malheureusement, la découverte de ces "meilleurs tests connus" est en réalité une recherche dans un domaine énorme (en fait infini). En 1980, une première liste de tests utiles a été créée par Carl Pomerance (célèbre pour avoir été celui qui a à factoriser 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 énorme domaine de recherche.
Voir ici pour plus d'informations : http://primes.utm.edu/prove/prove2_3.html y http://forums.nvidia.com/index.php?showtopic=70483
Si vous avez simplement 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 nombre entier n, vous pouvez utiliser le test de Lucas-Lehmer pour vérifier les nombres premiers de Mersenne. Un nombre premier de Mersenne est de 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 le mettre en œuvre en utilisant Nvidia CUDA, écrivez un noyau pour CUDA et exécutez-le sur le GPU.
Vous pouvez même gagner de l'argent si vous découvrez des nombres premiers suffisamment grands. L'EFF offre des prix allant de 50 000 à 250 000 dollars : https://www.eff.org/awards/coop
Votre problème est-il de décider si un nombre particulier est premier ? Dans ce cas, vous avez besoin d'un test de primalité (facile). Ou bien vous avez besoin de tous les nombres premiers jusqu'à un nombre donné ? Dans ce cas, les tamis de nombres premiers sont utiles (facile, mais nécessite de la mémoire). Ou bien 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 nombres dont vous avez besoin ? 16 bits ? 32 bits ? plus grands ?
Une méthode intelligente et efficace consiste à pré-calculer des tables de nombres premiers et à les conserver dans un fichier en utilisant un codage au niveau des bits. Le fichier est considéré comme un long vecteur binaire où le bit n représente l'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 bit) et ne nécessite pas de charger le fichier en mémoire.
Cela dépend de votre application. Il y a quelques considérations à prendre en compte :
Les tests de Miller-Rabin et analogiques ne sont plus rapides qu'un tamis pour les nombres supérieurs à une certaine taille (quelques millions, je crois). En dessous, l'utilisation d'une division d'essai (si vous n'avez que quelques nombres) ou d'un tamis est plus rapide.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
0 votes
Un vieil article que j'ai trouvé, mais qui semble intéressant : S'amuser avec les nombres premiers
29 votes
@Jaider cela échoue pour des nombres aussi bas que 7 (111). Elle échoue également pour 1001=9. Et il est clair que cela échoue pour presque tous les nombres premiers en général (cela ne couvre pas le cas 2^p - 1, qui sont des nombres premiers de Mersenne - exemples générés classiquement - qui seront toujours de la forme 111...1).
2 votes
@Kasperasky - Vous n'avez pas mentionné quel tamis ? Vous voulez probablement dire le tamis d'Eranthoses !
0 votes
Le tamis d'Eratosthène algorithme