Nombres premiers: crible d'Eratosthène

Soyez le premier à donner votre avis sur cette source.

Vue 3 938 fois - Téléchargée 577 fois

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 

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

KX
Messages postés
16136
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
23 mars 2020
92
"Il serait intéressant de traduire les 8 lignes du code Sieve3 en C ou C++ super-optimisé. Qui se propose de le faire ?"

En C :

#include "stdlib.h"

char* sieve3(int m)
{
    int i,j,p,pp, h=(m-1)/2;
    char* sv = malloc(sizeof(char)*h);
    
    for (i=0; i<h; i++)
        sv[i] = 1;
    
    for (i=0, p=3, pp=9; pp<=m; i++, p+=2, pp = p*p)
        if (sv[i])
            for (j=(pp-3)/2; j<h; j+=p)
                sv[j] = 0;
    
    return sv;
}

Remarque 1 : je propose une légère optimisation, en remplaçant pp=p*p par pp+=(p-1)<<2, mais je ne suis pas certain que cela améliore vraiment le calcul...

Remarque 2 : vu que le type booléen n'existe pas en C, j'ai mis des char, du coup la mémoire sera en char[Max/2], mais de toute façon je ne sais pas comment est gérée la mémoire en JavaScript mais un booléen prend surement aussi un octet en mémoire comme le char du C.

Voici un main de test :

#include "stdio.h"

int main()
{
    int i,m;
    char* sv;
    
    printf("m=");
    scanf("%d",&m);
    
    sv = sieve3(m);
    
    for (i=0; i<(m-1)/2; i++)
        printf("%d : %sn", 3+2*i, sv[i] ? "premier" : "pas premier");
    
    return 0;
}
KX
Messages postés
16136
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
23 mars 2020
92 > KX
Messages postés
16136
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
23 mars 2020

Après avoir fait quelques tests, j'en arrive à dire que mon "optimisation" est inutile, j'obtiens une différence de 0.02%, ce n'est donc pas pertinent.

Par contre (et sans surprise), c'est bien plus rapide en C qu'en JavaScript, même s'il faudrait faire des tests comparables, notamment sur la même machine.

max = 100000000
temps = 461 ms (moyenne de 100 exécutions)
William VOIROL
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
> KX
Messages postés
16136
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
23 mars 2020

Bonjour KX

Merci pour votre commentaire: la traduction que vous proposez est très bien faite.
Vous m'avez encouragé de me "remettre" à C et de présenter prochainement une "optimisation" basée sur votre fonction.
De plus, comme je soupçonne que Javascript utilise 64 bits par booléen, je vais essayer d'ajouter ici un "Sieve4.js" où sv est basé sur un string.
KX
Messages postés
16136
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
23 mars 2020
92 > William VOIROL
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019

En C on peut optimiser la mémoire en gérant soi même les bits.
On aurait donc pour chaque char un groupe de 8 bits que l'on associerait à 8 booléens.

Exemple :

char* reserve(int n)
{
    return malloc(n/8+1);
}

void set(char* tab, int i, int b)
{
    if (b)
        tab[i/8] |= (1 << i%8);
    else
        tab[i/8] &= ~(1 << i%8);
}

int get(char* tab, int i)
{
    return (tab[i/8] >> (i%8))%2 != 0;
}

On adapte alors facilement le programme avec ces nouvelles fonctions, et on optimise ainsi la consommation mémoire :

char* sieve3(int m)
{
    int i,j,p,pp, h=(m-1)/2;
    char* sv = reserve(h);
    
    for (i=0; i<h; i++)
        set(sv,i,1);
    
    for (i=0, p=3, pp=9; pp<=m; i++, p+=2, pp = p*p)
        if (get(sv,i))
            for (j=(pp-3)/2; j<h; j+=p)
                set(sv,j,0);
    
    return sv;
}

Cependant, comme on rajoute des opérations, on diminue aussi la rapidité du programme. On ne peut pas tout avoir...

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.