Sujet Précédent Sujet Suivant

Décomposer un nombre en nombre premiers

cs_Averell Messages postés 48 Date d'inscription mercredi 27 novembre 2002 Statut Membre Dernière intervention 9 juin 2016 - 9 juin 2016 à 20:21
William VOIROL Messages postés 261 Date d'inscription mardi 12 décembre 2006 Statut Membre Dernière intervention 10 juin 2019 - 7 juil. 2016 à 23:00

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

William VOIROL Messages postés 261 Date d'inscription mardi 12 décembre 2006 Statut Membre Dernière intervention 10 juin 2019
7 juil. 2016 à 23:00

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.

Discussions similaires

Calcul du n-ième nombre premier

génerateur de nombre aléatoire

Nombre de semaines dans l'année

decomposition d'un nombre en java

Nombre Premier

Votre réponse

Discussions similaires