Mon crible d'Eratosthène
Description
Le crible d'Eratosthène est une méthode très ancienne qui permet de calculer les nombres premiers compris entre 1 et une limite n donnée.
Le principe consiste à marquer dans la liste des entiers positifs tous les multiples des nombres premiers pris dans l'ordre où on les trouve dans la liste. La méthode s'arrête quand on a traité ou dépassé la racine carrée de la limite. Les nombres qui n'ont pas été marqués sont les nombres premiers recherchés.
Pour gagner un peu de temps dans le calcul du crible et pour gagner de la place mémoire pour son implantation, on a décidé que les multiples de 2, 3, 5 et 7 ne seront pas présents ni traités dans le crible. Cela entraine d'en tenir compte ensuite quand on veut exploiter le crible calculé ainsi. L'intérêt principal de ce programme réside dans la variante de la méthode de base ainsi définie. De plus, tout le source est disponible ici, on n'utilise aucune bibliothèque extérieure de programmes.
Une fois le crible calculé on a un mode conversationnel avec les commandes :
- combien y a-t-il de nombres premiers entre 1 et un nombre donné ?
- un nombre donné est-il premier ou composé ?
- quel est le rang du nombre premier ou composé donné ?
- quel est le nombre premier qui suit un nombre donné ?
- quel est le nombre premier ayant le rang donné ?
- quitter l'application
Le programme est compilé avec MicroSoft Visual Studio 2012 Express for Windows Desktop. Il utilise les entiers sur 8 octets et fonctionne en mode console sous Windows 64 bits. Le source est largement commenté. Pour marquer un nombre du crible un seul bit suffit. On peut noter que la limite demandée pour le crible peut atteindre et dépasser plusieurs centaines de milliards ( chacune : 100 000 000 000 ).
Il y a aussi une autre version compilée pour Windows 32 bits (x86). Cette version utilise les entiers de type "unsigned int" sur 4 octets. Le source ci-joint montre les très peu nombreuses modifications qui en résultent. Pour cette version la limite de l'exploration maximum est de : 4 294 311 961 et son explication est dans le source.
Les performances de ce programme sont bonnes, notamment au regard de la possibilité de dépasser la limite des entiers sur 32 bits pour l'intervalle d'exploration.
On peut noter que le source est mono-fichier et qu'on utilise des variables globales. Habituellement ceci ne plait pas aux puristes du C++ mais ici la lecture du source en est facilitée.
Il y a un supplément d'informations dans le fichier explications.txt et un mode d'emploi dans le fichier emploi.txt
Source :
/*************************************************************
* 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;
}
}
Conclusion :
Merci pour vos commentaires et remarques.Codes Sources
A voir également
- Mon crible d'Eratosthène
- Crible d'eratosthene - Forum C
- Crible quadratique - Forum Visual Basic
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.