Nombres premiers Algo/JS

Version imprimable

Bonjour
j''ai cree un algo qui permet d'afficher les nombres premiers de 1 à 100 ,
voivi l'algo
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 VARIABLES i EST_DU_TYPE NOMBRE b EST_DU_TYPE NOMBRE c EST_DU_TYPE NOMBRE DEBUT_ALGORITHME POUR i ALLANT_DE 1 A 100 DEBUT_POUR b PREND_LA_VALEUR 0 POUR c ALLANT_DE 2 A (sqrt(i)) DEBUT_POUR SI (i%c == 0) ALORS DEBUT_SI b PREND_LA_VALEUR 1 FIN_SI FIN_POUR SI (b == 0) ALORS DEBUT_SI AFFICHER* i FIN_SI FIN_POUR FIN_ALGORITHME
et j'ai essayé de resaisir le meme code sous JS mais sans resultats. il ne fonctionne pas :piou:

10/11/2017, 15h53
Watilin

Citation:

Envoyé par Popo3005

il ne fonctionne pas :piou:

Avec ça on est bien avancés. Si tu nous montrais ce que tu as essayé, et les résultats que ça a donné ?

j'ai essayé ça

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
<HTML>
    <BODY>
	    <SCRIPT type="text/Javascript">
                 for (i=1; i<=100; i++)
                        {for (j=2;j<=(sqrt(i));j++)
                                {a=i%j;
                                        if (a==0)
                                        {alert("0");
                                        continue;
                                        }
                                        alert(i);
                                }
                        }       
                </SCRIPT>
    </BODY>
</HTML>

petite précision c'est le code js qui marche pas

10/11/2017, 20h24
mathieu

la fonction "sqrt" n'existe pas. C'est la méthode "Math.sqrt" qu'il faut utiliser.
11/11/2017, 01h58
Watilin
C’est dommage les déclarations de variables qui sont parties aux oubliettes… C’est pourtant une bonne habitude à prendre.
JavaScript est faiblement typé mais ça ne nous empêche pas de déclarer les variables avec var ou let.
Code:

1 2 let i, j, a; for (i=1; ... // etc
Le mode strict permet de repérer rapidement les variables qui n’ont pas été déclarées. Si tu débutes en JS, je te conseille fortement d’adopter immédiatement le mode strict pour tous tes projets. Crois-moi, ça te rendra la vie plus facile :)

alert c’est sympa mais ça interromp l’exécution et ça requiert à chaque fois une intervention à la main pour continuer. Pour déboguer des scripts plus longs, ça se révèle vite fastidieux. Remplace tous les alert par des console.log puis ouvre la console de ton navigateur avec F12. Tu verras, c’est bien plus pratique ;)

c'est vrai qu'avec console.log c’est bien plus pratique.
J'ai autre problème
ce script
Code:

1 2 3 4 5 6 7 8 9 10 11 <HTML> <BODY> <SCRIPT type="text/Javascript"> for (i=2; i<=100; i++) {for (j=2;j<=(Math.sqrt(i));j++) {a=i%j; if (a==0) {alert(i);}}} </SCRIPT> </BODY> </HTML>
affiche les nombres non premiers à partir de 4
mais celui ci
Code:

1 2 3 4 5 6 7 8 9 10 11 <HTML> <BODY> <SCRIPT type="text/Javascript"> for (i=2; i<=100; i++) {for (j=2;j<=(Math.sqrt(i));j++) {a=i%j; if (a!=0) {alert(i);}}} </SCRIPT> </BODY> </HTML>
affiche les nbres premiers tels que 5 ;7 mais il affiche aussi 9;10;16;21
vous auriez une idée du probléme??

11/11/2017, 14h22
Watilin
Ton idée d’utiliser le modulo est bonne, cependant ton algo ne fait pas exactement ce que tu veux. Il ne détermine pas les nombres premiers, mais des couples de nombres qui sont premiers entre eux. Et pas tous (par exemple, 10 et 7 sont premiers entre eux mais ton algo ne le détecte pas car 7 est supérieur à la racine carrée de 10).

Avec une toute petite modification dans ton code, tu peux t’en rendre compte :
Code:

1 2 3 4 5 6 7 8 9 10 11 for (i = 2; i <= 100; i++) { for (j = 2; j <= (Math.sqrt(i)); j++) { a = i % j; if (a != 0) { console.log(`(${i}, ${j})`); } } }
(je me suis permis de reformater ton code avec http://jsbeautifier.org/)

Ce nouveau code affiche en sortie :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 (5, 2) (7, 2) (9, 2) (10, 3) (11, 2) (11, 3) (13, 2) (13, 3) (14, 3) (15, 2) (16, 3) (17, 2) ...
Il faut que tu revoies ton algorithme. Tu vas devoir procéder par élimination, à la manière du crible d’Ératosthène. En disant ça, j’en ai déjà trop dit, je vais te laisser chercher ;)

Merci bcp de votre aide le crible d'érasthosténe j'y avais penser mais là le travail est bcp plus long.Je ne sais pas si je peux le raccourcir:koi:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
	var nbr_pre =[3,5,7,11,13,17] ,
        length = nbr_pre.length,
	min = nbr_pre[length-1] + 2,
    max = parseInt(prompt('Nombre maximum :'));  
for (var nbr = min; nbr < max; nbr += 2) {
    var isPrime = true, moitier = (nbr + 1) / 2;
    for  (var id in nbr_pre) {
        if (!isPrime) {
            break;
        }
        if (nbr_pre[id] < moitier) {
            var reste_nbr = nbr % nbr_pre[id];
            if (reste_nbr == 0) {
                isPrime = false
            }
        }
        else {
            break;
        }
    }
    if (isPrime) {
        nbr_pre.push(nbr);
    }
}
 
for (var id in nbr_pre) {
    console.log(nbr_pre[id]);
}

Salut

Code:

1
2
3
4
5
6
7
8
9
10
let nbr, i, j
for (i = 2; i <= 100; i++)
{
    nbr = 0;
    for (j = 1; j <= (Math.sqrt(i)); j++)
    {
        if (i % j == 0) {nbr += 1;}
    } //--- for j ---
    if (nbr == 1){console.log(i);}
} //----- for i ---

12/11/2017, 21h13
Popo3005

Merci beaucoup pour le script:P
12/11/2017, 22h00
Beginner.

On nous avez donné cet exercice dans ce forum : ici, voici quelle était ma réponse : http://jsbin.com/tenaguyage/edit?js,console

On nous avez pas demandé d'optimiser avec la racine carrée mais c'est facile à ajouter comme ProgElecT l'a montré... On pourrait combiner les optimisations en ajoutant un break et unelse au code de ProgElecT...

Et si on veut du très concis voir la réponse de Sylvain...

Je me suis ré-intéressé au problème ces derniers jours;

http://javatwist.imingo.net/premiers.htm

j'arrive à mon meilleur timing avec ce code:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 <html> <head> <meta charset="iso-8859-1" /> <title>...</title> <style type="text/css"> #premiers{margin:auto;text-align:center;max-width:500px} </style> </head> <body> <div id="premiers"></div> <script> let tab=[2,3,5,7,11,13]; let i=17; console.time("t"); while(i<1000000){ if(i%3>0 && i%5>0 && i%7>0 && i%11>0 && i%13>0){ let n;let j=17; while (j*j<=i){if(i%j===0){n=true;break};j+=2;} if(!n){tab.push(i)}};i+=2;}; document.getElementById("premiers").textContent=tab.join(" ") console.timeEnd("t"); </script> </body> </html>
- Les conditions sur les 6 premiers nombres premiers permettent de gagner quelques millisecondes non négligeables;
- regrouper les conditions dans une boucle prend plus de temps;
- Plus ou moins de conditions ponctuelles ont tendance à augmenter le temps;
- whilefait gagner un peu de temps par rapport à for;
- une décrémentation avec while ne génère aucun progrès;
- tester que le nombre n'est divisible par aucun élément de tab prend plus de temps;
- etc.

Et vous, vous en êtes où en terme d'optimisation ???

après nouveaux tests, itérer sur tab donne de bons résultats;

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
console.time("t");
let tab=[3,5,7,11,13];
let i=17;
while(i!==1000001){
	if(i%3>0 && i%5>0 && i%7>0 && i%11>0 && i%13>0){
		let n, j=4;
		while (tab[j]**2<=i){if(i%tab[j]<1){n=true;break};j++;}	
		if(!n){tab.push(i)}
	};
	i+=2;
};
document.getElementById("premiers").textContent=2+" " +tab.join(" ")
console.timeEnd("t");