Nombres premiers: Crible fondamental (A)

Télécharger le projet
Commenter

Description

Bonjour,

Voici une ébauche personnelle concernant le calcul de nombres premiers.
Le théorème fondamental de l'arithmétique est utilisé pour traiter le crible d'Eratosthène.

Enoncé du théorème fondamental de l'arithmétique:
(aussi appelé: théorème de décomposition en produit de facteurs premiers)
Tout entier strictement positif peut être écrit comme un produit de nombres premiers d'une unique façon, à l'ordre près des facteurs.

Décomposition en facteurs premiers

Revenons d'abord sur le code CodeS-SourceS: Décomposition en facteurs premiers.
Voici une version légèrement adaptée contenue dans le fichier Decomp.html: 
<!DOCTYPE html>
<html><head>
  <title>Décomposition en facteurs premiers</title>
  <meta name='Author' content='William VOIROL, Switzerland, Oct 2016'/>
  <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)
  <br><input type='text' id='inp' onchange='Fac(this.value)'/>
  <small> < by William Voirol, Switzerland, Oct 2016 ></small>
  <br/><div id='out'> </div>
</body></html>
Un exemple d'utilisation est montré sur le fichier Decomp.jpg.

Nombres 2 à 10000 décomposés en facteurs premiers

Adaptons le programme précédent pour afficher les nombres de 2 à 10000 décomposés en facteurs premiers Decomp2aN.html: 
<!DOCTYPE html>
<html><head>
  <title>2 à n décomposés en facteurs premiers</title>
  <meta name='Author' content='William VOIROL, Switzerland, Oct 2016'/>
  <script>
    function Fact(n) {
      var s='';
      for (var nb=2; nb<=n; ++nb) {
        var m=nb,div=2,mul='';
        s+=((nb%10==0)?'<br>':' ')+m+'=';
        while (m>=div*div) {
          var i=0;
          while (m%div==0) {m/=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 (m>1) s+=mul+m;
      }
      document.getElementById('out').innerHTML=s;
    }
  </script>
</head><body style='background-color:yellow' onload='Fact(10000)'>
  <h3>2 à 10000 décomposés en facteurs premiers:</h3>
  <div id='out'></div><br>
  <small> (Oct 2016, by William Voirol, Switzerland.)</small>
</body></html>
Le résultat se trouve dans le fichier Decomp2aN.pdf.

Algorithme récursif

L'algorithme, pour calculer les premiers <= nn, est principalement composé de 3 parties:
- Calculer les premiers <= n (nn=n*n) avec CalPrm(n).
- Eliminer les éléments composés de facteurs premiers <= n.
- Eliminer ceux composés d'un (seul) facteur premier > n et de facteurs premiers <= n.

L'élimination des éléments composés de facteurs premiers <= n se fait à l'aide de la fonction récursive function Recur(k,a).
La même fonction Recur(k,a) peut être utilisée pour éliminer les éléments composés d'un facteur premier > n.

Le théorème fondamental nous garantit que tous les éléments composés sont éliminés.
Et même qu'ils ne sont éliminés qu'une seule fois !

Fichier FondaA.html: 
<!DOCTYPE html>
<html><head>
  <title>Nombres premiers: Crible fondamental - algorithme récursif</title>
  <meta name='Author' content='William VOIROL, Switzerland, Oct 2016'/>
  <script>
    var cb,pm;
    function CalPrm(n) { // calcule les petits nombres premiers <= n
      var m=~~((n+1)/2),cb=new Uint8Array(m),pm=[2];
      cb.fill(1);
      for (var i=1,c=3; c*c<=n; ++i,c+=2)
        if (cb[i])
          for (var k=~~((n-c)/c/2); k>=i; --k)
            if (cb[k]) cb[i+c*k]=0;
      for (var i=1,k=0; i<m; ++i) if (cb[i]) pm[++k]=2*i+1;
      return pm;
    }
    function FndRec(nn) { // pm contient les nombres premiers <= √nn
      var l=pm.length-1;
      cb=new Uint8Array(nn+1);
      cb[0]=cb[1]=0;
      for (var c=2; c<=nn; ++c) cb[c]=1; // initialise le crible cb

      for (var k=0; k<=l; ++k) Recur(k,pm[k]);  // élimine les éléments
      // composés uniquement de facteurs premiers contenus dans pm

      for (var c=pm[l]+1; c<=nn; ++c) // élimine les éléments formés de
        if (cb[c]) Recur(0,c); // produits composés d'un premier hors de pm

      function Recur(k,a) { // élimine les produits de la forme b=a{*pm[i>=k]}
        for (var i=k,b; (i<=l)&&((b=a*pm[i])<=nn); ++i) {cb[b]=0; Recur(i,b);}
      }
    }
    function Ini() {
      var z='<h3>Crible fondamental: algorithme récursif</h3>';
      for (var mm=10; mm<=100000000; mm*=10) {
        var np=0,t=new Date().getTime();
        pm=CalPrm(~~Math.sqrt(mm))
        FndRec(mm);
        t=new Date().getTime()-t;
        for (var c=0; c<=mm; ++c) if (cb[c]) np++; // cb[c]!=0: c est premier
        z+=np+'/'+mm+': '+t+' ms</br>';
      }
      z+='<br> <small>Oct 2016, William Voirol, Switzerland</small>';
      document.getElementById('Lst').innerHTML=z;
    }
  </script>
</head><body onload='Ini()'>
  <div id='Lst'> </div>
</body></html>
Ce code récursif est environs 7 fois plus lent que Avare-A !
J'avoue que je m'attendais à mieux, car cet algorithme me semble assez "élégant": il n'élimine qu'une seule fois un élément du crible !

Je vois deux voies qui pourraient améliorer les choses:
- Traiter l'algorithme de manière non récursive.
- Découvrir un autre moyen de parcourir les éléments du crible

Je n'ai trouvé aucun texte sur cet algorithme basée sur le théorème fondamental de l'arithmétique.
Serait-elle originale ?
Merci d'avance pour d'éventuelles références à d'autres écrits !

<gras>Liens<gras>:
WikipédiA: Théorème fondamental de l'arithmétique
William Voirol: Nombres premiers
CodeS-SourceS: Décomposition en facteurs premiers
CodeS-SourceS: Nombres premiers: Le crible avare A

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)