Nombres premiers Algo/JS

**Popo3005** · 10/11/2017, 06h19

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**Watilin** · 10/11/2017, 15h53

Envoyé par Popo3005

il ne fonctionne pas

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

**Popo3005** · 10/11/2017, 18h12

j'ai essayé ça

Code HTML :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**mathieu** · 10/11/2017, 20h24

la fonction "sqrt" n'existe pas. C'est la méthode "Math.sqrt" qu'il faut utiliser.

**Watilin** · 11/11/2017, 01h58

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**Popo3005** · 11/11/2017, 08h30

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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??

**Watilin** · 11/11/2017, 14h22

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**Popo3005** · 11/11/2017, 18h45

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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]);
}

**ProgElecT** · 11/11/2017, 23h17

Salut

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ---

**Popo3005** · 12/11/2017, 21h13

Merci beaucoup pour le script

**Beginner.** · 12/11/2017, 22h00

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...

**javatwister** · 25/01/2020, 14h28

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 html :

Sélectionner tout - Visualiser dans une fenêtre à part

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 ???

**javatwister** · 26/01/2020, 16h43

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

Code javascript :

Sélectionner tout - Visualiser dans une fenêtre à part

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");

Nombres premiers Algo/JS

JavaScript

Discussions similaires

Partager

Partager