Nombres premiers: Crible d'Atkin

Télécharger le projet
Commenter

Description

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

Nombres premiers: Crible d'Atkin


Voir: Crible d'Atkin

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

Atkin0.js


Pour commencer, voici un code 'classique' qui correspond au pseudo-code donné par WickyPedia sous le titre "Sieve of Atkin": 
function Atkin(mx) { // Atkin0.js
  var i,n,x,y,yy,r=Math.floor(Math.sqrt(mx));
  var sv=[false,false,true,true]; // for 0,1,2,3
  for (i=4; i<mx; i++) sv[i]=false;
  for (x=1; x<=r; x++) {
    var xx=x*x;
    for (y=1; y<=r; y++) {
      yy=y*y;
      n=3*xx-yy;
      if (x>y && n<=mx && (n%12==11)) sv[n]=!sv[n];
      n=3*xx+yy;
      if (n<=mx && (n%12==7)) sv[n]=!sv[n];
      n=4*xx+yy;
      if (n<=mx && (n%12==1||n%12==5)) sv[n]=!sv[n];
    }
  }
  for (n=5; n<=r; n++)
    if (sv[n]) for (x=n*n,i=x; i<=mx; i+=x) sv[i]=false;
  for (i=0,n=0; i<=mx; i++) if (sv[i]) n++; // i is prime
  return n;
}

Test direct
 
 

Atkin1.js


Optimisons le calcul des valeurs utilisées dans les boucles: 
function Atkin(mx) { // Atkin1.js
  var d,i,n,x,y,xx,xx3,yy,r=Math.floor(Math.sqrt(mx));
  var sv=[false,false,true,true]; // for 0,1,2,3
  for (i=4; i<=mx; i++) sv[i]=false;
  for (x=1,xx=1,xx3=3; xx<=mx; x++,xx=x*x,xx3=3*xx)
    for (y=1,yy=1; yy<=mx; y++,yy=y*y) {
      n=xx3-yy; if (x>y && n<=mx && (n%12==11)) sv[n]=!sv[n];
      n+=yy+yy; if (n<=mx && (n%12==7)) sv[n]=!sv[n];
      n+=xx;    if (n<=mx && (n%12==1||n%12==5)) sv[n]=!sv[n];
    }
  for (n=5; n<=r; n++)
    if (sv[n]) for (x=n*n,i=x; i<=mx; i+=x) sv[i]=false;
  for (i=0,n=0; i<=mx; i++) if (sv[i]) n++; // i is prime
  return n;
}

Test direct
 
 

Atkin2.js


Faisons 3 boucles internes adaptées aux limites particulières: 
function Atkin(mx) { // Atkin2.js
  var d,i,n,x,y,xx,yy,r=Math.floor(Math.sqrt(mx));
  var sv=[false,false,true,true]; // for 0,1,2,3
  for (i=4; i<=mx; i++) sv[i]=false;
  for (x=1; x<=r; x++) {
    xx=3*x*x;
    for (y=1; y<x; y++) if ((n=xx-y*y)<=mx && (n%12==11)) sv[n]=!sv[n];
    if (xx<mx)
      for (y=1; y<=r; y++) if ((n=xx+y*y)<=mx && (n%12==7)) sv[n]=!sv[n];
    xx+=x*x;
    if (xx<mx)
      for (y=1; y<=r; y++) if ((n=xx+y*y)<=mx && (n%12==1||n%12==5)) sv[n]=!sv[n];
  }
  for (n=5; n<=r; n++)
    if (sv[n]) for (x=n*n,i=x; i<=mx; i+=x) sv[i]=false;
  for (i=0,n=0; i<=mx; i++) if (sv[i]) n++; // i is prime
  return n;
}

Test direct
J'avoue que je suis un peu déçu de mes résultats obtenus.
Pourrait-on obtenir une amélioration significative en ne traitant que les impairs ? L'adaptation ne semble pas très simple.
Ou quelqu'un connaitrait-il une meilleure version de cet algorithme ?
 
 

Mesures


Le tableau ci-dessous, qui n'a qu'une valeur comparative, montre que les "meilleurs" codes basés sur l'algorithme "crible d'Askin" sont pratiquement limités aux 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] 
 Atkin0  0  0  3  29  407  4801  bool[Max] 
 Atkin1  0  0  3  30  384  4777  bool[Max] 
 Atkin2  0  0  5  37  360  4154  bool[Max] 

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)