Nombres premiers: essais de division avec liste

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.
 
 

Liste de nombres premiers obtenus par essais de division


Avantage de l'algorithme: temps d'exécution amélioré (on ne divise que par les nombres premiers déjà obtenus).
Désavantage: utilise un tableau des nombres premiers calculés.
 
 

List0.js


Pour utiliser les améliorations du groupe "Essais de division" nous nous basons directement sur le code du fichier "Div4.js". Chaque fois qu'un nombre premier est trouvé, nous l'ajoutons à la liste lst : 
function List(m) { // List0.js: return list of prime numbers <= m
  var lst=[2]; // 2 is prime
  for (var c=3,n=1,r=1; c<=m; c+=2) { // c: candidate
    var b=true;
    if (r*r<=c) r++;
    for (var d=3; d<r; d+=2)
      if (c%d==0) {b=false; break;}
    if (b) lst[n++]=c; // c is prime
  }
  return lst;
}

Test direct
 
 

List1.js


Comme nous disposons des nombres premiers plus petits que le nombre candidat, nous pouvons limiter les diviseurs à ces nombres premiers: 
function List(m) { // List1.js: return list of prime numbers < m
  var lst=[2];
  for (var c=3,n=1,r=1; c<=m; c+=2) {
    var b=true;
    if (r*r<=c) r++;
    for (var d=2,q=3; q<r; q=lst[d++])
      if (c%q==0) {b=false; break;}
    if (b) lst[n++]=c; // c is prime
  }
  return lst;
}

Test direct
 
 

ListOut.html


Utilise aussi "List1.js" (ainsi que "Out.js").
N'affiche pas le temps d'exécution, mais tous les nombres premiers <= max dans une textarea A.
Le temps d'affichage est nettement amélioré en écrivant en une seule fois dans la textarea un string s contenant tous les nombres trouvés: A.value=s, plutôt qu'en augmentant le contenu avec chaque nombre premier: A.value += lst[i]+" " (comme proposé presque partout).
Essai direct: ListOut
 
 

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 
 List0  0  1  26  323  7301  -  int[n] 
 List1  0  1  19  172  2557  -  int[n] 

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)