Nombres premiers: crible d'Eratosthène

Télécharger le projet
Commenter

Description

Pour la définition, voir "Nombres premiers: essais de division"
Une version actualisée de l'introduction, complétée de mesures des temps d'execution, peut être obtenue ICI.
 
 

Crible d'Eratosthène


Voir: Crible d'Eratosthène

Avantage de l'algorithme: temps d'exécution rapide et programmation simple.
Désavantage: utilise un tableau (bool) de tous les nombres candidats.
 
 

Sieve0.js


Pour commencer, voici un code 'classique' qui, lorsqu'on a trouvé un nombre premier,
on annule tous ses multiples (dans le tableau sv): 
function Sieve(m) { // Sieve0.js
  var sv=[false,false]; // sv=new Array(m+1)
  for (i=2; i<=m; i++) sv[i]=true;
  for (i=2; i<=m; i++)
    if (sv[i]) // i is prime
      for (j=i+i; j<=m; j+=i) sv[j]=false;
  return sv;
}

Test direct
 
 

Sieve1.js


Comme pour la méthode des essais de division, on peut se limiter aux candidats
dont le carre est plus petit que m: 
function Sieve(m) { // Sieve1.js
  var i,j,sv=[false,false]; // sv=new Array(m+1)
  for (i=2; i<=m; i++) sv[i]=true;
  for (i=2; i*i<=m; i++)
    if (sv[i]) // i is prime
      for (j=i+i; j<=m; j+=i) sv[j]=false;
  return sv;
}

Test direct
 
 

Sieve2.js


Voici une adaptation personnelle de l'algorithme qui ne traite que les nombres
pairs (à part 2). Dans le tableau sv, le candidat correspondant à l'index i
n'est pas i lui-même, mais p=3+2*i comme représenté ici: 
// i  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ...
// p  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 ...
//    #       +3       +3       +3       +3       +3       +3       +3       ...
//       #             +5             +5             +5             +5       ...
//          #                   +7                   +7                   +7 ...
//                #                              +11                         ...
//                   ...

function Sieve(m) { // Sieve2.js: m>=3
  var h=1+Math.floor((m-3)/2),i,j,p,sv=[]; // sv=new Array(h)
  for (i=0; i<h; i++) sv[i]=true;
  for (i=0,p=3; p*p<=m; i++,p+=2)
    if (sv[i]) // p is prime
      for (j=i+p; j<h; j+=p) sv[j]=false;
  return sv; // 2 is not included
}

Ceci divise la mémoire utilisée par 2 le temps de calcul quasiment par 4 !
Test direct
 
 

Sieve3.js


On peut commencer à éliminer les candidats multiples de p à partir de pp=p*p,
d'index (pp-3)/2, car les plus petits ont déjà été enlevés. 
// i  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 ...
// p  3  5  7  9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 ...
//    #       +3       +3       +3       +3       +3       +3       +3       ...
//       #                            +5             +5             +5       ...
//          #                                                             +7 ...
//                #                                                          ...
//                   ...
                    
function Sieve(m) { // Sieve3.js: m>=3
  var h=1+Math.floor((m-3)/2),i,j,p,pp,sv=[]; // sv=new Array(h)
  for (i=0; i<h; i++) sv[i]=true;
  for (i=0,p=3,pp=9; pp<=m; i++,p+=2,pp=p*p)
    if (sv[i]) // p is prime
      for (j=(pp-3)/2; j<h; j+=p) sv[j]=false;
  return sv; // 2 is not included
}

Test direct
Il serait intéressant de traduire les 8 lignes du code Sieve3 en C ou C++ super-optimisé. Qui se propose de le faire ?

Le traitement de nombres épurés des multiples de 2 et de 3 sera la première étape du groupe "Crible avec cycle additif".
 
 

Mesures


Le tableau ci-dessous, qui n'a qu'une valeur comparative, montre que les "meilleurs" codes basés sur l'algorithme "crible d'Eratosthène" sont pratiquement limités au nombres premiers inférieurs à 100 millions.
Les mesures dépendent de l'ordinateur, du navigateur et de leur charge.
Sur le même ordinateur, j'ai chaque fois effectué une série de tests et indiqué le meilleur résultat.

Temps d'execution en ms:
 Max:  1000  10000  100000  1000000  10000000  100000000   
 n:  168  1229  9592  78498  664579  5761455  memory: 
 Div0  2  63  3365  -  -  -  0 
 Div1  1  42  1770  145128  -  -  0 
 Div2  0  2  35  309  7579  -  0 
 Div3  0  2  31  305  6799  -  0 
 Div4  0  1  30  296  6564  -  0 
 List0  0  1  26  323  7301  -  int[n] 
 List1  0  1  19  172  2557  -  int[n] 
 Sieve0  0  1  11  79  659  7104  bool[Max] 
 Sieve1  0  1  9  63  466  5003  bool[Max] 
 Sieve2  0  1  2  20  142  1495  bool[Max/2] 
 Sieve3  0  0  1  23  138  1455  bool[Max/2] 


Accédez aux tests et sources de tous mes travaux sur les nombres premiers ICI (sous Maths, Nombres premiers)
 
 Testé avec: 
 Firefox  22.0  OK 
 Google Chrome  28.0  OK 
 Internet Explorer  10.0.7  OK 
 Opera  22.0   OK 
 Safari   22.0  OK 
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

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.

Du même auteur (William VOIROL)