Nombres premiers: crible des multiplications
Le principe de l'algorithme consiste à parcourir la
table de multiplication pour neutraliser dans le crible (sv) chaque élément qui correspondant à un produit.
Vous trouverez la description originale sous
Nombres premiers: crible des multiplications.
Comme Javascript est loin d'être performant, je présente ici une "optimisation en C" de quelques codes.
Une version actualisée de l'introduction aux nombres premiers, complétée de mesures des temps d'exécution, peut être obtenue ici
Nombres premiers.
Autres liens sur les nombres premiers:
Essais de division
Essais de division avec liste
Crible d'Eratosthène
Crible d'Eratosthène (optimisation C)
Crible d'Atkin
Remarque: Les codes qui suivent ne font que "remplir" le crible et utilisent:
typedef unsigned _int32 u32;
MultA.cpp
Traduisons d'abord du code Javascript
Mult7.js en C et ajoutons un "main()" pour le tester:
bool *Mult(u32 mx, u32 &h) { // MultA "Crible des produits": mx > 9
u32 a=(mx-5)%6,d,j,k,u,v,xy[2];
h=((mx-5-a)/3+((a>1)?4:3)); // nombre de bits significatifs du crible
bool *sv=(bool*)malloc(h*sizeof(bool));
for (k=0; k<h; k++) sv[k]=true;
for (j=2,d=9,u=0,v=8; d<h; d+=(++j&1)? u+=8: v+=16)
if (sv[j]) {
if (j&1) {xy[0]=2*j-1; xy[1]=4*j-3;} else {xy[0]=4*j-1; xy[1]=2*j-1;}
for (k=d; k<h; k+=xy[k&1]) sv[k]=false;
}
return sv;
} // William Voirol, Switzerland
Temps d'exécution (fichier MultA.cpp):
MultA (Crible des produits):
m=10, n=4, t=0 ms
m=100, n=25, t=0 ms
m=1000, n=168, t=0 ms
m=10000, n=1229, t=0 ms
m=100000, n=9592, t=0 ms
m=1000000, n=78498, t=0 ms
m=10000000, n=664579, t=16 ms
m=100000000, n=5761455, t=390 ms
m=1000000000, n=50847534, t=4804 ms
On peut extraire du crible la liste des nombres premiers p (à partir de 5) avec la boucle
for (i=2,p=5; i<h; p+=cyc[i&1],i++) if (sv[i]) { /* p is prime */ }
MultB.cpp
Puis optimisons la mémoire en n'utilisant qu'un seul bit par élément du crible.
Après quelques mesures, j'ai constaté une amélioration de quelques % du temps d'exécution en utilisant les 32 bits d'un unsigned _int32 plutôt que les 8 bits d'un unsigned char, comme souvent conseillé.
u32 *Mult(u32 mx, u32 &h) { // MultB "Crible des produits": mx > 9
u32 a=(mx-5)%6,d,j,k,n,u,v,xy[2];
h=((mx-5-a)/3+((a>1)?4:3)); // nombre de bits significatifs du crible
u32 *sv=(u32*)malloc((n=(h+31)/32)*sizeof(u32)); // 8 bits par byte => 32 bits par u32
for (j=0; j<n; j++) sv[j]=0XFFFFFFFF; // All true
for (j=2,d=9,u=0,v=8; d<h; d+=(++j&1)? u+=8: v+=16)
if (sv[j>>5]&(1<<(j&31))) {
if (j&1) {xy[0]=(j<<1)-1; xy[1]=(j<<2)-3;} else {xy[0]=(j<<2)-1; xy[1]=(j<<1)-1;}
for (k=d; k<h; k+=xy[k&1]) sv[k>>5]&=(~(1<<(k&31))); // SetFalse
}
return sv;
} // William Voirol, Switzerland
Temps d'exécution (fichier MultB.cpp):
MultB (Crible des produits):
m=10, n=4, t=0 ms
m=100, n=25, t=0 ms
m=1000, n=168, t=0 ms
m=10000, n=1229, t=0 ms
m=100000, n=9592, t=0 ms
m=1000000, n=78498, t=0 ms
m=10000000, n=664579, t=15 ms
m=100000000, n=5761455, t=171 ms
m=1000000000, n=50847534, t=3650 ms
Surprise, nous gagnons sur les deux tableaux: mémoire utilisée et temps d'éxecution !!!
On peut extraire du crible la liste des nombres premiers p (à partir de 5) avec la boucle
for (i=2,p=5; i<h; p+=cyc[i&1],i++) if (sv[i>>5]&(1<<(i&31))) { /* p is prime */ }
Pour essayer de situer le dernier code
MultB par rapport à d'autres qui permettent également de déterminer le crible d'Eratosthène avec une valeur maximale mx <= 4'294'709'602 (correspondant à 203'268'793 nombres premiers), je donne quelques mesures (même ordinateur et compilateur):
(année, temps d'exéc., mémoire, lien):
2003, 53.461 s, bit[Max/2],
1 000 000 de nombres premiers en 0.062 secondes
2011, 63.773 s, bit[Max/2],
crible d'eratosthène optimisé
2013, 23.167 s, bit[Max/2],
Nombres premiers: crible d'Eratosthène
2013, 17.659 s, bit[Max/3],
MultB (fichier MultB-Max.cpp)
Aidez-moi à améliorer, compléter ou corriger cette liste.
Voir aussi
Nombres premiers.
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.