Calcul du n-ième nombre premierRésolu

Question

Bonjour, Je souhaite une méthode C++ qui calcule le n-ième nombre premier aussi rapidement que possible. Cette fonction doit être appelée pour une valeur de n ou bien pour quelques unes seulement et surtout pas pour toutes les valeurs de n. J'ai donc écrit : #include #include #include int prem(int n) { // calcul du n-ième nombre premier int i, k, d, s, x; std::vector p; if(n == 1) return 2; if(n == 2) return 3; if(n == 3) return 5; p.push_back(2); p.push_back(3); p.push_back(5); // pour : p[0]=2, p[1]=3, p[2]=5, p[3]=7, etc. x = 5; k = 3; s = 4; while(k != n) { // pour x : 7, 11, 13, 17, 19, 23, 25, etc. // ce qui évite les multiples de 2 et 3 s = 6 - s; x = x + s; d = 5; i = 2; while((d*d <= x) && (x%d != 0)) d = p[i++]; // quand tous les diviseurs d éventuels ont été // essayés, alors x est premier si : d*d > x if(d*d > x) { p.push_back(x); k++; } } return x; } void main() { int n = 1; for(int i=0; i<8; i++) { clock_t start = clock(); std::cout << "prem(" << n << ") : " << prem(n) << " en : "; std::cout << double(clock()-start)/double(CLOCKS_PER_SEC) << " s" << std::endl; n = n * 10; } } Et j'obtiens ceci : prem(1) : 2 en : 0 sprem(10) : 29 en : 0 sprem(100) : 541 en : 0 sprem(1000) : 7919 en : 0 sprem(10000) : 104729 en : 0 sprem(100000) : 1299709 en : 0.093 sprem(1000000) : 15485863 en : 1.922 sprem(10000000) : 179424673 en : 52.11 s Comment faire pour aller plus vite et plus loin ? Tous mes remerciements. --

Whismeril · Answer

Salut, William Voirol s'est pas mal penché sur le sujet.
http://codes-sources.commentcamarche.net/source/s/u/William%20VOIROL%20CRIBLE/last

pgl10 · Answer

Bonjour Whismeril,
Moi aussi je me suis intéressé au crible d'Ératosthène, j'ai même effectué un envoi à CCM-CS à ce sujet : 
http://codes-sources.commentcamarche.net/source/100217-mon-crible-d-eratosthene 
mais cela sert à trouver tous les nombres premiers plus petits qu'une limite donnée, ce n'est pas du tout le traitement qui est souhaité ici. Merci quand même.
--

pgl10 · Answer

Bonjour,
En cherchant sur Internet une solution au problème, on en trouve plusieurs. Voici donc une référence qui calcule le n-ième nombre premier et qui fournit les sources et l'exécutable : https://github.com/kimwalisch/primecount Les performances sont vraiment extraordinaires. J'ai obtenu les résultats suivants :

Ce qui est remarquable. La méthode utilisée est bien plus efficace mais elle est aussi beaucoup plus complexe à analyser et à comprendre. Une méthode plus simple me conviendrait même si les performances étaient un peu moins bonnes !
--

KX · Answer

Bonjour,

Si tu regardes le code de nth_prime.cpp tu verras qu'au delà de 10 000 la formule utilisées est celle de Dana Jacobsen, mais c'est une approximation, ce qui explique pourquoi c'est aussi rapide (on privilégie la vitesse à la qualité).

Tu en trouveras une explication sur son blog universitaire :
http://search.cpan.org/~danaj/Math-Prime-Util-0.45/lib/Math/Prime/Util.pm#nth_prime

Les problèmes d'arithmétiques sont souvent très intéressant, mais comprendre des algorithmes très poussés relèvent du casse tête !

Pourtant aussi vieux soit il, la crible d'Erathostène, même si elle construit tous les nombres premiers est encore très utilisé car elle se parallélise bien. Il faut donc réfléchir multithread.

pgl10 · Answer

Bonjour KX,
Merci beaucoup pour ces références et explications complémentaires. En regardant de plus près l'une et l'autre je vois que Kim Walisch privilégie la vitesse et la qualité. 

Si j'ai bien compris, il utilise la formule de Dana Jacobsen pour s'approcher de la réponse exacte et il effectue en complément une petite étape de crible pour terminer rapidement le calcul et obtenir la réponse finale. Les réponses que j'ai obtenues et que j'ai pu vérifier sont toutes exactes. De plus, Kim Walisch utilise le multithread avec OpenMP. 

A noter aussi que cet auteur diffuse "primecount" pour calculer le n-ième nombre premier et "primesieve" pour générer et compter les nombres premiers jusqu'à n avec autant d'efficacité. Il est indiqué à https://primes.utm.edu/nthprime/index.php que ses logiciels y sont utilisés.
--

KX · Answer

Dans tes tests tu n'es pas allé très loin, 10^18 c'est assez raisonnable.
Pour des calculs de cryptographie (où les nombres premiers interviennent beaucoup) on est sur des nombres premiers de l'ordre de 2^2048, 2^4096.
À cette échelle là, je doute que l'algorithme approché soit exact. D'ailleurs on a introduit la notion de nombre premiers probables et de nombres pseudo-premiers, parce qu'il y a un doute raisonnable quant à leur primalité.

Remarque : si je parlais de passer à la parallélisation, je ne parlais pas pour ceux qui ont fait ces programmes, mais pour toi qui cherchait un algorithme à la fois plus performant que ton code et plus simple que les codes que tu as trouvé sur internet.

pgl10 · Answer

Merci beaucoup d'avoir précisé ces renseignements complémentaires. En discutant j'ai avancé aujourd'hui bien plus vite sur le sujet. J'espère que cela servira aussi à d'autres membres.
--

pgl10 · Answer

Bonjour tous, Dans mon petit programme ci-dessus on peut remarquer que le tableau p[] est rempli avec les nombres premiers jusqu'au n-ième nombre premier recherché. C'est beaucoup plus qu'il n'en faut, ils ne sont utilisés que jusqu'à environ sqrt(n-ième nb prem). Cette limite n'est pas connue. Mais en raison de la raréfaction des nombres premiers vers les grands nombres on peut se limiter à sqrt(n). Ce qui donne : #include #include #include int prem(int n) { // calcul du n-ième nombre premier int i, k, m, d, s, x; std::vector p; if(n == 1) return 2; if(n == 2) return 3; if(n == 3) return 5; p.push_back(2); p.push_back(3); p.push_back(5); // pour : p[0]=2, p[1]=3, p[2]=5, p[3]=7, etc. x = 5; k = 3; s = 4; m = 1 + (int)sqrt(double(n)); while(k < m) { // pour x : 7, 11, 13, 17, 19, 23, 25, etc. // ce qui évite les multiples de 2 et 3 s = 6 - s; x = x + s; d = 5; i = 2; while((d*d <= x) && (x%d != 0)) d = p[i++]; // quand tous les diviseurs d éventuels ont été // essayés, alors x est premier si : d*d > x if(d*d > x) { p.push_back(x); k++; } } while(k < n) { s = 6 - s; x = x + s; d = 5; i = 2; while((d*d <= x) && (x%d != 0)) d = p[i++]; if(d*d > x) k++; } return x; } void main() { int n = 1; for(int i=0; i<8; i++) { clock_t start = clock(); std::cout << "prem(" << n << ") : " << prem(n) << " en : "; std::cout << double(clock()-start)/double(CLOCKS_PER_SEC) << " s" << std::endl; n = n * 10; } } Cela fait un gain relatif de mémoire très important. Mais les temps d'exécution sont à peu près les mêmes. Et j'ai aussi essayé de remplacer std::vector p; par un simple tableau d'entiers : cela ne va pas plus vite non plus, ce qui est un bon renseignement sur l'efficacité du vecteur d'entiers relativement au tableau d'entiers. --

KX · Answer

Bonjour,

"ils ne sont utilisés que jusqu'à environ sqrt(n-ième nb prem)"
Tu as du voir passé dans tes recherches la fonction &pi;(x) qui est une approximation du nombre de nombres premiers entre 0 et x, mais ça ne fait pas intervenir la racine carrée, il faut plutôt penser aux logarithmes...

Une propriété pour x&ge;55 : x/(ln x + 4) < &pi;(x) < x/(ln x - 2)

Par exemple pour 1 000 000, cela donne un intervalle entre 56 130 et 84 634 (la valeur exacte étant 78 498), d'autres formules peuvent affiner l'intervalle, mais en tout cas on est loin de la la racine carrée qui donne 1 000...

"l'efficacité du vecteur d'entiers relativement au tableau d'entiers"
En réalité la classe std::vector utilise en interne un tableau, il est automatiquement redimensionné donc c'est transparent, mais au final c'est la même chose.
À la limite ça pourrait même être pire d'utiliser un vecteur à cause de l'étape de redimensionnement du tableau qui peut être coûteuse en temps et en mémoire.
La bonne pratique avec les vecteurs est donc de leur donner une taille initiale suffisante pour que le tableau ne soit jamais redimensionné.

pgl10 · Answer

Bonjour KX,
Oui, je connais les diverses approximations de la fonction &pi;(x) mais pour m'en servir pour x = 1 + sqrt(n-ième nb prem) il y a une difficulté : je ne connais pas le n-ième nb prem, c'est ce que je souhaite calculer. Par contre, je sais parfaitement que ma limite k < m est beaucoup trop grande. Pour n = 1000000 je devrais stocker dans p[] les nombres premiers qui sont utiles jusqu'à p[547] mais avec m = 1 + (int)sqrt(double(n));  je vais jusqu' à p[1001] ( ce qui est trop, c'est vrai ! ). Cependant c'est beaucoup moins que p[1000000], le gain de mémoire est donc déjà très bon et comme les temps d'exécution sont environ les mêmes que ceux obtenus obtenus avec le stockage complet jusqu'à n, le pofinage avec &pi;(x) ne donnerait rien de bien mieux : le temps d'exécution serait environ le même et le gain principal de mémoire serait déjà obtenu. En résumé : en passant à k < m on gagne en mémoire et on ne gagne rien en temps d'exécution et si on cherche à passer à x < xmax avec &pi;(x) on n'aura pas un gain en temps d'exécution et le gain en mémoire sera mieux mais pas excessivement mieux.
--

cs_pseudo3 · Answer

Bonjour,

Une curiosité : Pour tout nombre premier P(N) supérieur ou égal à 7 on peut toujours trouver au moins un couple de premiers P(J)  et P(K) tels que  P(N) = P(J) + P(K) ± 1.

Et avec la Relation P(N) = P(J) + P(J-1) ± 1 est-t-il Premier pour J  = 2 à 1228 ?
On trouve 730 premiers
Pour 2454 P(N) testés
Non premiers dans plage (*) sans premier : 2 (donc évitables)
Non premiers car divisibles par 3,5,7,9,11 ou 13 : 1231 (donc évitables)
Score : 100*730 /(2454 - 2 - 1231) = 59,78 % de premiers

(*) : Plages du style "Il n'existe aucun nombre premier entre n! + 2 et n! + n et idem entre n! - 2 et n! - n"

Il faudrait pouvoir trouver la relation qui relie entre eux  les indices J et K tels que Somme = P(J) + P(K) ± 1 soit toujours nombre premier : avis aux amateurs

pgl10 · Answer

Bonjour tous,
Finalement j'ai fait un autre essai. Je prends une valeur supérieure au nombre cherché avec une approximation de &pi;(x) et je fais ensuite un crible  d'Eratosthène de 1 à cette valeur. Il suffit ensuite de parcourir les résultats du crible pour trouver le n-ième nombre premier recherché. Selon cette méthode le temps d'exécution est nettement meilleur que ci-dessus. Les commentaires de Wismeril et de KX allaient déjà dans ce sens. Merci, bye.
--

Calcul du n-ième nombre premier

12 réponses

Votre réponse

Discussions similaires