0/5 (2 avis)
Vue 20 289 fois - Téléchargée 1 069 fois
/************************************************************* * Crible d'Eratosthène par pgl10 * * * * Pour gagner de la mémoire et du temps d'exécution on ne * * marque pas dans le crible les multiples de 2, 3, 5 et 7 * * Après avoir calculé le crible on a les fonctions : * * - prem(n) : le nombre n est-il premier ? * * - next(n) : le nombre premier qui suit l'entier n * * - nieme(n) : la valeur du n-ième nombre premier * * - nbprem(n) : le nombre de premiers entre 1 et n * * Ce programme fonctionne correctement au-delà de * * plusieurs fois 10^11 ( 100 000 000 000 ) * *************************************************************/ #include <iostream> #include <iomanip> #include <cstdint> #include <ctime> int64_t nc; // limite de l'intervalle [1,nc] de calcul du crible int64_t nmax = 300000000000; // 300 000 000 000 // nmax est la valeur maximum de nc. // Pour un crible de (2^32)-1 = 4294967295 octets, // nc est compris entre 150323855292 et 150323855327 // On peut choisir arbitrairement nmax = 150323855327 // Mais une valeur plus grande de nmax est admissible. unsigned char* crible; // crible[] contient les bits utiles du crible. int64_t seqnc[48]; // La séquence répétitive des nombres marqués dans le crible. int64_t cycle[48]; // cycle[i] = seqnc[i+1] - seqnc[i] int64_t nb[210]; // Les rangs de la séquence répétitive du crible. int nk[256]; // nk[i] est le nombre de bits contenus dans l'octet i (de 0 à 255) bool done=false; // done est mis à la valeur true quand les nk[] sont calculés unsigned char c0[8]={'xFE', 'xFD', 'xFB', 'xF7', 'xEF', 'xDF', 'xBF', 'x7F'}; unsigned char c1[8]={'x01', 'x02', 'x04', 'x08', 'x10', 'x20', 'x40', 'x80'}; // Suivant la méthode du crible d'Eratosthène on va marquer // à 1 les bits du crible pour les nombres premiers de 1 à n // et à 0 pour les nombres composés. // Mais pour gagner du temps et de l'espace mémoire les multiples // de 2, 3, 5 et 7 ne seront ni présents ni marqués dans le crible. // Chaque élément du crible aura les bits marqueurs pour 8 entiers. // crible[0] pour 11, 13, 17, 19, 23, 29, 31, 37 // crible[1] pour 41, 43, 47, 53, 59, 61, 67, 71 // crible[2] pour 73, 79, 83, 89, 97, 101, 103, 107 // crible[3] pour 109, 113, 121, 127, 131, 137, 139, 143 // crible[4] pour 149, 151, 157, 163, 167, 169, 173, 179 // crible[5] pour 181, 187, 191, 193, 197, 199, 209, 211 // crible[6] pour 221, 223, 227, 229, 233, 239, 241, 247 // etc. 121 est le 1-er nombre composé du crible et 143 le 2-ième. // Tous les 2*3*5*7 = 210 valeurs les nombres marqués dans crible // recommencent une séquence identique décalée de la valeur 210. // Dans le crible elle occupe 48 bits successifs seulement (6 octets). // Après avoir rempli le tableau nb[210] avec les rangs successifs // le nombre i sera marqué par le p-ième bit du crible avec // p = ((i-11)/210)*48 + nb[(i-11)%210]; dans l'octet q=p/8 // à la position r=p-8*q et inversement le p-ième bit du crible // est le marqueur du nombre i = (p/48)*210 + seqnc[p%48] void pause() { std::cout << std::endl; system("pause"); } void limite() { std::cout << std::endl << "L'intervalle de calcul est trop grand" << std::endl; pause(); exit(EXIT_FAILURE); } // L'entier i est-il dans le crible ? bool filtre(int64_t i) { if(i%2==0) return false; if(i%3==0) return false; if(i%5==0) return false; if(i%7==0) return false; return true; } // Crible d'Ératosthène void Eratosthene() { int64_t i, i2, j, ni, nj, p, q, r, t; // Pour p de 0 à 47 les nombres seqnc[p] sont les // nombres de la séquence répétitive du crible. p=0; for(i=11; i<221; i++) { if(filtre(i)) { seqnc[p]=i; p=p+1; } } // Pour p de 0 à 47 cycle[p] est la différence entre // le (p+1)-ième nombre marqué et le p-ième. for(i=0; i<47; i++) cycle[i]=seqnc[i+1]-seqnc[i]; // cycle[47]=seqnc[0]+210-seqnc[47]=221-211 cycle[47]=10; // Pour i de 0 à 209, si le nombre i+11 ( de 11 à 220 ) // est marqué, il est dans le crible au nb[i]-ième bit, // et si non nb[i] = le rang du nombre marqué précédent. p=-1; for(i=0; i<210; i++) { if(filtre(i+11)) p=p+1; nb[i]=p; } q=1+((nc-11)/210*48+nb[(nc-11)%210])/8; crible = new unsigned char[q]; if(crible == NULL) limite(); std::cout << std::endl << "Le crible a : " << q << " octets" << std::endl; std::cout << std::endl << "Attendre ... "; // Initialisation de crible[] : tous les marqueurs à 1 memset(crible, 'xFF', q); // Selon la méthode habituelle, on va marquer par un bit nul les multiples de // chaque nombre premier à partir de 11 en évitant les multiples de 2, 3, 5 et 7 i=11; i2=121; ni=nj=0; while(i2<=nc) { p=(i-11)/210*48+nb[(i-11)%210]; q=p/8; r=p-8*q; if((crible[q]&c1[r]) != 'x00') { // La majorité du temps CPU se passe // dans la boucle interne suivante for(j=i2; j<=nc;) { t=(j-11)/210*48+nb[(j-11)%210]; q=t/8; // Pour marquer à 0 le nombre composé j multiple de i // on pourrait aussi faire : crible[q]&=~(1<<(t&7)); crible[q]&=c0[t-8*q]; // Le j suivant sera le prochain multiple de i // non multiple de 2, 3, 5 ou 7 j=j+cycle[nj%48]*i; nj=nj+1; } } i=i+cycle[p%48]; nj=ni=ni+1; i2=i*i; } }
3 janv. 2014 à 20:04
Modifié par pgl10 le 3/01/2014 à 13:34
On peut facilement utiliser le crible d'Eratosthène pour vérifier ou bien pour rechercher diverses particularités concernant les nombres premiers. En modifiant le programme principal main() {} selon ce que l'on souhaite, on peut obtenir des résultats amusants. Par exemple, le polynôme p(x)=13x5-130x4+455x3-650x2+312x+93287 donne la valeur 93287, c'est un nombre premier, pour x = 0, 1, 2, 3 et 4 mais en plus il donne consécutivement 19 nombres premiers depuis x = 0 jusqu'à x = 18. Y a-t-il un polynôme qui donne 5 nombres premiers identiques pour x de 0 à 4 donnant consécutivement plus de 19 nombres premiers ? Y a-t-il un polynôme plus simple donnant consécutivement 19 nombres premiers, ou plus, dont les 5 premiers sont identiques ?
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.