Décomposer un nombre en nombre premiers

Signaler
Messages postés
48
Date d'inscription
mercredi 27 novembre 2002
Statut
Membre
Dernière intervention
9 juin 2016
-
Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019
-
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/101514-decomposer-un-nombre-en-nombre-premiers

Messages postés
261
Date d'inscription
mardi 12 décembre 2006
Statut
Membre
Dernière intervention
10 juin 2019

Bonjour,

J'ai essayé le code présenté.
Voici quelques remarques:

a) 1 (un) n'est pas premier selon la définition habituelle !!!

b) En entrant 5'000'000 comme valeur initiale, j'ai entendu 15 minutes (montre en main) pour voir apparaître la liste de nombres premiers jusqu'à cette valeur.

c) Une fois la liste calculée, l'entier à décomposer est limité à la valeur initiale.

d) Ensuite, en entrant 4'500'000 pour en obtenir sa décomposition en facteurs premiers, Firefox a planté.

e) En consultant Nombres premiers, on constate qu'il y existe des algorithmes (en Javascript) qui calculent les nombres premiers <= 10'000'000 en moins d'une seconde.

f) Avec par exemple CycleOut dans Nombres premiers, on obtient la liste des nombres premiers <= 5'000'000 en moins de 2 secondes.

g) Le codes suivant:
<!DOCTYPE html>
<html><head>
  <title>Décomposition en facteurs premiers</title>
  <script>
    function Fac(val) {
      var div=2, nb=parseInt(val,10),s='<br>'+nb+' = ', mul='';
      if (isNaN(nb)||(nb<=1)||(nb>=9007199254740992))
        {alert('nombre incorrect !'); return;}
      while (nb>=div*div) {
        var i=0;
        while (nb%div==0) {nb/=div; ++i;}
        if (i>0) {s+=mul+div; mul='•';}
        if (i>1) s+='<sup>'+i+'</sup>';
        ++div; // ou:  if (div<3) div=3; else div+=2;
      }
      if (nb>1) s+=mul+nb;
      document.getElementById('out').innerHTML+=s;
    }
  </script>
</head><body style='background-color:yellow'>
  Entrez un nombre entre 2 et 9007199254740991 (= 2<sup>53</sup>-1) :  
  <input type='text' id='inp' onchange='Fac(this.value)'/>
  <br/><div id='out'></div>
</body></html>
montre qu'il n'est pas nécessaire de d'abord calculer une liste de nombres premiers pour obtenir instantanément la décomposition d'un nombre même entre 2 et 9007199254740991.

h) La remarque "Comme c'est en javascript, c'est super lent" me semble ici inappropriée.