Nombres premiers: Le crible avare A

Télécharger le projet
Commenter

Description

Bonjour,

L'algorithme du crible avare correspond à un développement personnel sur les nombres premiers.
L'adjectif avare s'explique à l'aide des trois "économies" suivantes:
A) Chaque élément clandestin du crible n'est éliminé qu'une seul fois.
B) Utilisation d'un crible épuré des multiples de quelques petits premiers.
C) Chaque élément du crible est formé d'un seul bit.

Cet article est limité au traitement du point A).

Avare.html

Partons de Nombres premiers: crible d'Eratosthène pour écrire un premier code: 
var crb=new Uint8Array(mm+1);

function Avare(mm) { // crb.length = mm+1
  for (var c=0; c<=mm; ++c) crb[c]=(c<2)?0:1;
  for (var c=2; c*c<=mm; c++)
    if (crb[c]) // c est premier
      for (var cc=c*c; cc<=mm; cc+=c) crb[cc]=0;
}

Résultats et temps de calcul: 
Crible Avare:
4/10: 0 ms
25/100: 0 ms
168/1000: 0 ms
1229/10000: 0 ms
9592/100000: 0 ms
78498/1000000: 4 ms
664579/10000000: 110 ms
5761455/100000000: 1457 ms

AvareA.html

Utilisons l'amélioration correspondant à EratoD dans Le crible d'Eratosthène classique où chaque candidat clandestin n'est éliminé qu'une seule fois: 
var crb=new Uint8Array(mm+1);

function AvareA(mm) { // crb.length = mm+1
  for (var c=0; c<=mm; ++c) crb[c]=(c<2)?0:1;
  for (var c=2; c*c<=mm; c++)
    if (crb[c]) // c est premier
      for (var q=~~(mm/c); q>=c; --q)
        if (crb[q]) crb[c*q]=0;
}
Remarque: Le code UneSeuleFois.html permet de vous en persuader.

D'après Nombres premiers, les temps de calculs (en Javascript) sont actuellement les meilleurs. 
Crible AvareA:
4/10: 0 ms
25/100: 0 ms
168/1000: 0 ms
1229/10000: 0 ms
9592/100000: 0 ms
78498/1000000: 5 ms
664579/10000000: 62 ms
5761455/100000000: 639 ms


L'économie correspondant au point B) ci-dessus sera décrite dans le prochain article:
Nombres premiers: Le crible avare B et s'appuiera principalement sur Nombres premiers: Crible avec cycle additif et Nombres premiers: Crible avec cycle additif Bis.

Consultez le fichier Nombres premiers qui vous permet de comparer différents algorithmes.

Bonne lecture ...
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)