Nombres premiers: essais de division

Télécharger le projet
Commenter

Description


Définition des nombres premiers:


Un nombre entier (>1) est dit premier s'il n'admet aucun diviseur autre que 1 et lui-même.

Mon but est de familiariser les intéressés avec quelques codes concernant les nombres premiers.
Actuellement, j'ai prévu plusieurs "groupes":
 0-Div  Essais de division 
 1-List  Essais de division avec liste 
 2-Sieve  Crible d'Eratosthène 
 3-Atkin  Crible d'Atkin 
 4-Cycle   Crible avec cycle additif 
 5-Mult   Crible des multiplications 
 6-...   ... 

Chaque groupe est (ou sera) composé d'un code initial interprétant l'algorithme étudié, suivi d'améliorations "classiques" ou personnelles.
Tous les codes présentés sont d'édition propre (pas de copier-coller).

Une version actualisée de cette introduction, complétée de mesures des temps d'execution, peut être obtenue ICI.

Nombres premiers: essais de division


Dans cette première série de codes, on se contente de compter les nombres premiers c <= m (max donné), mais ils sont "explicites" à l'endroit commenté "// c is prime".
(pour visualiser des nombres premiers, voir la prochaine série "essais de division avec liste: ListOut")

Les codes proposées sont sous la forme de deux boucles imbriquées: 
...
for (c= ...) { // boucles des candidats c
  ...
  for (d= ... ) { ... } // boucle des diviseurs d
  ...
}

L'optimisation dans la boucle intérieure (diviseurs) sera donc pertinante.
 
 

Div0.js


Nous commençons par un code "classique" qui correspond à la définition de l'introduction.
Il comporte pourtant déjà une "optimisation": la boucle intérieure des diviseurs s'arrête au premier diviseur rencontré (break). 
function Div(m) { // Div0.js: naive
  var b,c,d,n=1; // 2 is prime
  for (c=3; c<=m; c++) {
    for (d=2,b=true; d<c; d++) if (c%d==0) {b=false; break;}
    if (b) n++; // c is prime
  }
  return n;
}

Test direct
 
 

Div1.js


Comme, à part 2, aucun entier pair n'est premier, nous allons nous limiter aux nombres impairs aussi bien dans la boucle des candidats c que dans celle des diviseurs d. 
function Div(m) { // Div1.js: optimization odd
  var b,c,d,n=1; // 2 is prime
  for (c=3; c<=m; c+=2) {
    for (d=3,b=true; d<c; d+=2) if (c%d==0) {b=false; break;}
    if (b) n++; // c is prime
  }
  return n;
}

Test direct
 
 

Div2.js


Il est facile de constater qu'on peut arrêter le test de division lorsque d*d dépasse c. 
function Div(m) { // Div2.js: optimization odd,square
  var b,c,d,n=1; // 2 is prime
  for (c=3; c<=m; c+=2) {
    for (d=3,b=true; d*d<=c; d+=2) if (c%d==0) {b=false; break;}
    if (b) n++; // c is prime
  }
  return n;
}

Test direct
 
 

Div3.js


Malheureusement, on doit calculer d*d dans la boucle intérieure des diviseurs. Il vaut mieux calculer r = ?c avant cette boucle pour pouvoir l'arrêter avec
un test simple d<=r . 
function Div(m) { // Div3.js: optimization odd,root
  var b,c,d,n=1; // 2 is prime
  for (c=3; c<=m; c+=2) {
    b=true,r=Math.floor(Math.sqrt(c));
    for (d=3; d<=r; d+=2) if (c%d==0) {b=false; break;}
    if (b) n++; // c is prime
  }
  return n;
}

Test direct
 
 

Div4.js


Le code du calcul d'une racine carrée est assez compliqué (il comporte plusieurs dizaines de multiplications ou divisions).
En tenant compte du fait que la racine carrée r d'un nombre augmente "moins vite" que le nombre lui-même, il suffit d'incrémenter r lorsque c'est nécessaire.
Selon mes recherches sur le web, cette petite "simplification" semble inédite: faites le moi savoir si je me trompe. 
function Div(m) { // Div4.js: optimization odd,*
  var b,c,r,n=1; // 2 is prime
  for (c=3,r=1; c<=m; c+=2) {
    if (r*r<=c) r++;
    for (d=3,b=true; d<r; d+=2) if (c%d==0) {b=false; break;}
    if (b) n++; // c is prime
  }
  return n;
}

Test direct
 
 

Mesures


Le tableau ci-dessous, qui n'a qu'une valeur comparative, montre que les "meilleurs" codes basés sur l'algorithme "essais de division" sont pratiquement limités au nombres inférieurs à 10 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 

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)