11486 sujets

JavaScript, DOM et API Web HTML5

Bonjour,
Il y a quelques jours, une question a ete posée (en php) sur l'affichage des nombres premiers sur les 1.000 premiers nombres. Pour m'amuser, je me suis demandé comment je ferais en JS. J'ai fait une premiere version où le nbre premier est affiché dès qu'il est trouvé mais ensuite j'ai voulu connaitre la vitesse d'execution du calcul et de l'affichage et j'ai fait la presente version...juste pour le plaisir de coder (qui n'est pas ma profession).
upload/1606086645-61012-nbrepremier01.png
Petite erreur sur le premier nbre, j avais mis 1 (d'où le 26 au lieu de 25 pour la 1ere centaine) !

<!DOCTYPE html>
<html lang="fr">
<head>
    <meta charset="UTF-8">
    <link rel="icon" type="image/png" href="./logo.png" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>Nombres premiers</title>
    <link rel="stylesheet" href="index.css">
</head>
<body>

    <div>
        <p>n = 
            <input type="number" id="inputn" name="inputn" min="200" step="100" value="200" /> premiers nombres.
            <br><button id="go"> Go</button>
        </p>
        <p>Vitesse d'execution :<br>
            - calcul : <span id="vitesseCalcul"></span> <br>
            - affichage : <span id="vitesseAffichage"></span> <br>
            - total : <span id="vitesseTotal"></span>
        </p>
    </div>
    <hr>
    <div>
         <p>Densité : <br> 
            - effectifs par table : <span id="densite"></span><br>   
            - moyenne : <span id="moyenne"></span><br>
            - écart : <span id="ecartMoyenne"></span><br>
            <span id="legendeEcart">| écart à la moyenne |</span> 
        </p>
    </div>

    <div id="selectAffiche">
        Affichage des tables
        <input type="radio" name="affiche" id="oui" value="oui" checked> oui
        <input type="radio" name="affiche" id="non" value="non"> non
    
        <p id="table"><!-- ici affichage des table --></p> 
    </div>
    
<script type="module" src="main.mjs"></script>
</body>
</html>



body{font-size: 14pt; margin:20px;}
#inputn{width: 80px;}
#go{margin-top: 15px; padding: 10px 30px 10px 30px;
    color: green; font-weight: bold; font-size: 14pt;}
#go:hover{color: firebrick;}

#vitesseCalcul{margin-left: 24px;}
#vitesseTotal{margin-left: 36px;}

#moyenne{margin-left: 10px;}
#ecartMoyenne{margin-left: 50px;}
#legendeEcart{font-size: 12px; color: grey; 
    margin-left: 8px; font-style: italic;}

hr{color: lightgrey;}

#selectAffiche{margin-top: 40px; }
#non{margin-left: 20px;}

#table{margin-top: -10px;}

.blue{color: rgb(10, 81, 212);}
.red{color: red;}

import {timer, speed} from './timer.mjs';
import {calculDesNp} from './calculDesNp.mjs';
import {calculDensite} from './calculDensite.mjs';
import {afficheTable} from './afficheTable.mjs';
import {afficheDensite} from './afficheDensite.mjs';
// ------------------------------------------

let buttonGo = document.getElementById('go');
buttonGo.addEventListener('click', function()
{
    let inputn = document.getElementById('inputn');  
    let n = inputn.value;
    n = parseInt(n, 10);
    
    // choix d'afficher ou non les tables
    // (input 'radio')
    let yes = document.getElementById('oui'); 
    let no = document.getElementById("non");

    let timerPrincipal = new timer(); 
    let timerCalcul = new timer();
    let timerAffichage = new timer();

    timerPrincipal.start();
        timerCalcul.start();
            let binaireTab = calculDesNp(n);
            let densite = calculDensite(binaireTab);
        timerCalcul.end();
        timerAffichage.start();
            if(no.checked == false){afficheTable(binaireTab);}
            afficheDensite(densite);
        timerAffichage.end();
    timerPrincipal.end();
    
    timerCalcul.duree = speed(timerCalcul.start, timerCalcul.end);
    timerAffichage.duree = speed(timerAffichage.start, timerAffichage.end);
    timerPrincipal.duree = speed(timerPrincipal.start, timerPrincipal.end);


    let spanCalcul = document.getElementById('vitesseCalcul');
    spanCalcul.innerHTML = ` <b>${timerCalcul.duree[0]}</b> mn : <b>${timerCalcul.duree[1]}</b> s : <b>${timerCalcul.duree[2]}</b> ms `;
    
    let spanAffichage = document.getElementById('vitesseAffichage');
    spanAffichage.innerHTML = ` <b>${timerAffichage.duree[0]}</b> mn : <b>${timerAffichage.duree[1]}</b> s : <b>${timerAffichage.duree[2]}</b> ms `;

    let spanPrincipal = document.getElementById('vitesseTotal');
    spanPrincipal.innerHTML = ` <b>${timerPrincipal.duree[0]}</b> mn : <b>${timerPrincipal.duree[1]}</b> s : <b>${timerPrincipal.duree[2]}</b> ms `;

    let table = document.getElementById('table');
    no.addEventListener('change', () => {
        if(no.checked==true){table.style.display='none';}
    });
    yes.addEventListener('change', () => {
        if(yes.checked==true){table.style.display='block';}
    });
});

// fichier 'timer.mjs'

export function timer()
{
    this.start = undefined,
    this.end = undefined, 
    this.duree = [0,0,0],

    this.start = start,
    this.end = end
}

function start(){this.start = new Date().getTime();}
function end(){this.end = new Date().getTime();}

export function speed(start, end)
{
        let duree, mn, s, ms;
        duree = end - start;

        if (duree < 1000){
                mn = 0; s = 0; ms = duree;
        } else {
                ms = Math.round(duree % 1000);
                s = Math.round(duree / 1000);
                mn = 0;
                if (s>=60){
                        mn = Math.round(s / 60);
                        s = Math.round(s % 60);
                }          
        }

        return [mn, s, ms];
}



// fichier 'calculDesNp.mjs

export function calculDesNp(n)
{
    // [] pre-rempli avec nbres premiers 
    // de l'intervale 0 à 9. 
    let listeDesNp = [2,3,5,7]; 
    
    // [] pre-rempli de l'intervale 0 à 9
    let binaireTab=[0,0,1,1,0,1,0,1,0,0]; 
    
    let premier;

    for(let i=10; i<n; i++)
    { 
        for(let x=0; x<listeDesNp.length; x++)
        {
            // comparaison de chaque nombre avec les 
            // np qui sont dans le [] listeDesNp 
            premier=true;
            if( !(i % listeDesNp[x]) ){premier=false; break;}
        }
        if(premier)
        {
            listeDesNp.push(i);
            binaireTab.push(1);
        }else{binaireTab.push(0);}
    }
    
    return binaireTab
}



// fichier 'calculDensite.mjs'

export function calculDensite(binaireTab)
{
    // densite <=> nbre de np par table

    let n = binaireTab.length;

    // nbreDeTable = nbreDeCentaine
    let nbreDeTable = binaireTab.length/100;

    let sommeParTable = new Array(nbreDeTable);
    sommeParTable.fill(0);
    sommeParTable[0]=4; // les 4 premiers np : 2 3 5 7 

    for(let i=10; i<n; i++)
    {    
        if(binaireTab[i]==1){
            if(i<100){sommeParTable[0]++;}

            for(let j=1; j<nbreDeTable; j++)
            {            
                if( i>(100*j) && i<(100*(j+1)) )
                    {sommeParTable[j]++;}
            }
        }
    }

    let len = sommeParTable.length;
    let reducer = (accumulator, currentValue) => accumulator + currentValue;

    let moyenne = sommeParTable.reduce(reducer) / len;
    moyenne = Math.round(moyenne * 100) / 100;

    let sommeEcartTab = sommeParTable.map( (item) => Math.abs(item-moyenne) );
    let ecart = sommeEcartTab.reduce(reducer)/len;
    ecart = Math.round(ecart * 100) / 100;

    return [sommeParTable, moyenne, ecart];
}

Modifié par alain_47 (23 Nov 2020 - 00:50)

// fichier 'afficheTable.mjs'

export function afficheTable(binaireTab)
{
    let n = binaireTab.length;
    let color; let content="";
    for(let i=0; i<n; i++)
    {
        if(i%100==0){content += '<br>';}
        if(i%10==0) {content += '<br>';}
        
        binaireTab[i]==1 ? color="red" : color="blue";

        content += '<span class="' + color + '">' + i + '</span> &nbsp;'; 
    }
 
    let table = document.getElementById('table');
    table.innerHTML = content;
}



// fichier 'afficheDensite.mjs'

export function afficheDensite(densite)
{
    let sommeParTable = densite[0];
    let moyenne = densite[1];
    let ecart = densite[2];

    document.getElementById('densite').innerHTML = sommeParTable;
    document.getElementById('moyenne').innerHTML = moyenne;
    document.getElementById('ecartMoyenne').innerHTML = ecart;
}

Modérateur
Bonjour,

Intéressant !

Ceci dit, la fonction ci-dessous (utilisant le crible d'Ératosthène) est sensiblement plus rapide tout en étant plus courte que la fonction que tu emploies pour le calcul des nombres premiers.

Par exemple (en désactivant le calcul des densités et l'affichage des tables afin de ne pas trop perturber la mesure), on obtient un résultat 1000 fois plus rapide pour n=1 000 000 avec cette fonction par rapport à ta fonction.

export function calculDesNp(n)
{
    // calcul des nombres premiers avec le crible d'Ératosthène
    let binaireTab=new Array(n);
    let i, j, i2=Math.floor(Math.sqrt(n));
	
    binaireTab[0]=0;
    binaireTab[1]=0;
    binaireTab.fill(1, 2);
	
    for(i=2; i<=i2; i++)
    { 
    	if(binaireTab[i])
    		for(j=(i*i);j<n;j+=i)
    			binaireTab[j]=0;
    }
    return binaireTab
}

Amicalement,
Modifié par parsimonhi (23 Nov 2020 - 09:32)
J'avais utilisé le tableau binaire 'binaireTab' : les 0 correspondent à 'pas premier' et 1 à 'premier'.

Donc si on veut savoir par exemple si le nombre 152789 est premier ou pas, il suffit de faire de consulter l'index binaireTab[152789] : si c'est 0 pas premier, si c'est 1 c'est un nombre premier.

C'est la premiere fois que j'utilise les 'import' , les 'include' de php sont legerement plus pratiques.
Modérateur
Bonjour,

alain_47 a écrit :
J'avais utilisé le tableau binaire 'binaireTab' : les 0 correspondent à 'pas premier' et 1 à 'premier'.


La fonction que je propose fait la même chose. Mais le principe du crible, c'est que au départ, on suppose que tous les nombres sont premiers (en mettant binaireTab[ i ] à 1), et au fur et à mesure qu'on avance, on "coche" ceux qui ne sont pas premiers (en mettant binaireTab[ i ] à 0).

Tu peux donc utiliser cette fonction à la place de la tienne. "Extérieurement", c'est le même résultat.

Amicalement,
Modifié par parsimonhi (23 Nov 2020 - 13:10)
Modérateur
Bonjour,
alain_47 a écrit :
impressionnant.
pour n= 1.000.000 , on passe de 13s à 1s.


En fait, 1s, c'est essentiellement le calcul de densité (que je n'ai pas cherché à optimiser). Sans le calcul de densité, tu passerais de 12s à 0.012s environ.

EDIT: pour retirer le calcul de densité dans l'estimation du temps, il suffit que tu mettes timerCalcul.end(); juste avant ce calcul de densité.

Amicalement,
Modifié par parsimonhi (23 Nov 2020 - 18:11)
Oui, merci.

Je m'étonnais de ne pas voir dans le code de calcul modulo.

En étudiant le code, je me suis rendu compte que la double boucle se substituait à modulo et le rendait inutile.

Pre-remplir de 1 et ajouter les zéros ensuite (alors que j'avais fait l'inverse), génial comme idée.

En faisant console.log , j'ai vu :

Pour n = 200 : sqrt_n = 14,14 arrondi à 14 (14 x 14 = 196)

i=2 : j = 4 à 198 step 2
i=3 : j = 9 à 198 step 3
i=5 : j = 25 à 195 step 5
i=7 : j = 49 à 196 step 7
i=11 : j = 121 à 198 step 11
i=13 : j = 169 à 195 step 13

Ce qui est fascinant, c'est qu'avec juste les nbres premiers inférieurs à la racine carree de 200, on puisse atteindre tous les numéros jusqu'à 200. Donc avec seulement les 6 premiers nombres premiers (sur les 56), on peut remplir le tableau jusqu'à 200. Il fallait y penser !

Bonne soirée.