Calcul du n-ième nombre premier [Résolu]

pgl10 304 Messages postés samedi 18 décembre 2004Date d'inscription 18 octobre 2018 Dernière intervention - 17 oct. 2014 à 10:38 - Dernière réponse : pgl10 304 Messages postés samedi 18 décembre 2004Date d'inscription 18 octobre 2018 Dernière intervention
- 20 oct. 2014 à 18:21
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 <iostream>
#include <vector>
#include <ctime>

int prem(int n) {
   // calcul du n-ième nombre premier
   int i, k, d, s, x;
   std::vector<int> 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 s
prem(10) : 29 en : 0 s
prem(100) : 541 en : 0 s
prem(1000) : 7919 en : 0 s
prem(10000) : 104729 en : 0 s
prem(100000) : 1299709 en : 0.093 s
prem(1000000) : 15485863 en : 1.922 s
prem(10000000) : 179424673 en : 52.11 s

Comment faire pour aller plus vite et plus loin ?
Tous mes remerciements.


--
Afficher la suite 

Votre réponse

12 réponses

Meilleure réponse
pgl10 304 Messages postés samedi 18 décembre 2004Date d'inscription 18 octobre 2018 Dernière intervention - Modifié par pgl10 le 18/10/2014 à 18:43
1
Merci
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.
--

Merci pgl10 1

Avec quelques mots c'est encore mieux Ajouter un commentaire

Codes Sources a aidé 104 internautes ce mois-ci

Commenter la réponse de pgl10
Whismeril 12117 Messages postés mardi 11 mars 2003Date d'inscriptionContributeurStatut 19 octobre 2018 Dernière intervention - 17 oct. 2014 à 13:52
0
Merci
Salut, William Voirol s'est pas mal penché sur le sujet.
http://codes-sources.commentcamarche.net/source/s/u/William%20VOIROL%20CRIBLE/last
Commenter la réponse de Whismeril
pgl10 304 Messages postés samedi 18 décembre 2004Date d'inscription 18 octobre 2018 Dernière intervention - 17 oct. 2014 à 15:32
0
Merci
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.
--
Commenter la réponse de pgl10
pgl10 304 Messages postés samedi 18 décembre 2004Date d'inscription 18 octobre 2018 Dernière intervention - 18 oct. 2014 à 13:51
0
Merci
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 !
--
Commenter la réponse de pgl10
KX 15783 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 20 octobre 2018 Dernière intervention - 18 oct. 2014 à 14:29
0
Merci
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.
Commenter la réponse de KX
pgl10 304 Messages postés samedi 18 décembre 2004Date d'inscription 18 octobre 2018 Dernière intervention - 18 oct. 2014 à 15:29
0
Merci
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.
--
Commenter la réponse de pgl10
KX 15783 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 20 octobre 2018 Dernière intervention - 18 oct. 2014 à 17:45
0
Merci
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.
Commenter la réponse de KX
pgl10 304 Messages postés samedi 18 décembre 2004Date d'inscription 18 octobre 2018 Dernière intervention - Modifié par pgl10 le 19/10/2014 à 10:28
0
Merci
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 <iostream>
#include <vector>
#include <ctime>

int prem(int n) {
   // calcul du n-ième nombre premier
   int i, k, m, d, s, x;
   std::vector<int> 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<int> 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.
--
Commenter la réponse de pgl10
KX 15783 Messages postés samedi 31 mai 2008Date d'inscriptionModérateurStatut 20 octobre 2018 Dernière intervention - 19 oct. 2014 à 13:13
0
Merci
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 π(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≥55 : x/(ln x + 4) < π(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é.
Commenter la réponse de KX
pgl10 304 Messages postés samedi 18 décembre 2004Date d'inscription 18 octobre 2018 Dernière intervention - Modifié par pgl10 le 19/10/2014 à 15:13
0
Merci
Bonjour KX,
Oui, je connais les diverses approximations de la fonction π(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 π(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 π(x) on n'aura pas un gain en temps d'exécution et le gain en mémoire sera mieux mais pas excessivement mieux.
--
Commenter la réponse de pgl10
pgl10 304 Messages postés samedi 18 décembre 2004Date d'inscription 18 octobre 2018 Dernière intervention - 20 oct. 2014 à 18:21
0
Merci
Bonjour tous,
Finalement j'ai fait un autre essai. Je prends une valeur supérieure au nombre cherché avec une approximation de π(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.
--
Commenter la réponse de pgl10
cs_pseudo3 - 20 oct. 2014 à 14:43
-1
Merci
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
Commenter la réponse de cs_pseudo3

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.