[défi n°8]: premiers nombres premiers

**javatwister** · 12/06/2005, 10h21

Bah, c'est plutôt inutile mais je vous propose de pondre un code minimal pour générer les nombres premiers de 1 à 1000 dans une simple alerte;

on pourra s'amuser à tester la rapidité d'interprétation avec 2 getTime()

ps: et non, je ne me suis pas converti aux mathématiques; là c'est juste de la détente

**troumad** · 12/06/2005, 10h25

Regarde ma page : http://troumad.free.fr/Math/nb_premiers.php

**javatwister** · 12/06/2005, 10h30

salut

Envoyé par troumad

Regarde ma page

euh... oui;

et alors?

**troumad** · 12/06/2005, 10h33

Envoyé par javatwister

et alors?

Ce n'est pas un exploit de vitesse, mais il y a un algo pour récupérer les nombres premiers. Pour l'exploit de vitesse, je te conseillerais plutôt une programmation en C ou assembleur

.

**javatwister** · 12/06/2005, 10h48

hum;

Je vais préciser pour le coup l'objectif de ces petits défis javascript

inciter à la mise en oeuvre de javascript dans des objectifs variés;

développer la curiosité, l'envie de découvrir et d'inventer chez les jeunes adeptes;

s''habituer à respecter des contraintes de fond ou de forme dans la création javascript / html

développer la lecture / compréhension de code (voir premiers défis)

donner l'occasion aux membres de partager leur connaissances et leurs idées sur des problèmes qui échappent un peu au quotidien du forum

finalement, donner la possibilité à tout le monde d'évoluer dans sa manière de coder, quel que soit son niveau;

J'ai beau être à l'initiative de la "rubrique", j'attends avec impatience le premier défi proposé par un autre que moi

Il est maladroit d'amener un script tout fait dans un topic "défi": le principe est de réinventer la roue, évidemment! seul moyen de comprendre vraiment le langage utilisé.

Enfin, ici, on n'utilise que les pouvoirs ridiculement modestes de javascript pour arriver à ses fins.

**troumad** · 12/06/2005, 10h56

Bon. Alors j'ai rajouté un bouton. Comme la monté à 1000 se fait en 11 milliseconde, j'ai fait une montée à 10000 afin de pouvoir mieux départager les algos (duron cadencé à 1300 MHz)..

nb : ce n'est pas mon dernier mot. Je trouverais peut-être d'autres accélérateurs !

**javatwister** · 12/06/2005, 12h11

très joli

tu peux le mettre en clair ici?

bon, le défi est lancé!

**troumad** · 12/06/2005, 14h26

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
function p_1000()
{
 t=new Date()
 prem = new Array
 for (i=3;i<=10000;i+=2)
  prem[i]=1;
 for (i=3;i<=10000;i+=2)
  if (prem[i])
   for (j=i;j*i<=10000;j+=2)
    prem[j*i]=0;
 t1=new Date()
 s="temps : "+(t1-t)+"   "
 for (i=3;i<=10000;i+=2)
  if (prem[i])
   s+=" "+i;
 alert(s)
}

C'est quoi les autres défis ?

**Celelibi** · 12/06/2005, 15h01

Salut Troumad,
Sur ta page, la première partie avec le tableau de 10*10 me rappel étrangement le crible d'Eratosthène.

D'ailleur une propriété interressante est que lorsque tu raye tous les multiples d'un nombre premier n, le premier nombre que tu vas rayer est n^2.

Tiens, je viens de voir qu'en fait ton algo pour chercher les nombre premiers n'est qu'une implémentation de ce crible d'Eratosthène.

Je ne pense pas que mon code puisse rivaliser avec celui du prof de math.

Moi je l'ai fait à l'ancienne (ou presque).

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
30
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
    <title>nombres premiers</title>
 
    <script type="text/javascript">
      function chercher() {
        var debut = (new Date).getTime();
        var premiers = new Array;
        premiers.push(1, 2);
        iter:
        for (var i=3; i<1000; i+=2) {
          var max = Math.sqrt(i);
          for (var j=1; premiers[j]<=max; j++) {
            if (!(i%premiers[j])) {
              continue iter;
            }
          }
          premiers.push(i);
        }
        var temps = (new Date).getTime() - debut;
        alert(temps);
        //alert(premiers.join(', '));
      }
    </script>
  </head>
  <body>
    <input type="button" value="Chercher" onclick="chercher()" />
  </body>
</html>

C'est vrai dans le genre "code minimal" on peut mieux faire, mais ça fait un moment que je fais du code lisible et optimisé plutôt que du code court.

Bon JT, après la trigo avec le billard, l'algèbre avec les nombres premier, on va avoir de la géométrie dans le plan la prochaine fois ?

Ou peut-être des probas (Troumad, ça te rappel quelque chose l'urne de bernoulli ?

)

**troumad** · 12/06/2005, 16h19

Envoyé par Celelibi

(Troumad, ça te rappel quelque chose l'urne de bernoulli ?

)

C'est ici que j'en avais parlé avec quelqu'un je crois !

**javatwister** · 12/06/2005, 16h34

bon alors voilà le fruit de mes longues années d'études mathématiques

zarbi, isn't it?

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
<script type="text/javascript"> 
 
r="1 3"
t=new Array()
 
for(i=3;i<10000;i+=2){
 
t[i]=i
 
for(j in t){
	if(i % j == 0) break
 
	if(j > i/j) {
		r+=" "+i
		break
	}
}
 
}
 
 
alert(r);
 
</script>

**Celelibi** · 12/06/2005, 17h36

Envoyé par troumad

Envoyé par Celelibi

(Troumad, ça te rappel quelque chose l'urne de bernoulli ?

)

C'est ici que j'en avais parlé avec quelqu'un je crois !

Oui c'était ici même, il y a environ un an, avec moi même. Le tout étant parti d'une question de quelqu'un cherchant à mélanger de façon aléatoire un tableau.

ps : finalement j'ai modifié mon code, et je descend dans les 6ms pour les nombres premiers de 1 à 1000 (contre 42 avec mon ancien code

)

**troumad** · 12/06/2005, 18h13

Envoyé par javatwister

r="1 3"

Les deux premiers nombres premiers sont 2 et 3

Envoyé par javatwister

for(i=3;i<10000;i+=2){

t[i]=i

for(j in t){
if(i % j == 0) break

if(j > i/j) {
r+=" "+i
break
}
}

Le problème dans ton cas est que l'affichage (r+=" "+i) est inclu dans le temps de calcul.

Envoyé par Celelibi

finalement j'ai modifié mon code, et je descend dans les 6ms pour les nombres premiers de 1 à 1000 (contre 42 avec mon ancien code

)

Tu as testé le mien ? Je monte à 10000 comme javatwister

**javatwister** · 12/06/2005, 18h32

mort de rire, t'as raison, j'en oublie le 2

en tout cas, je suis très loin de toi pour le temps! (autour de 160 pour 10000)

j'avoue que j'ai pas la force cosmique suffisante pour comprendre de vrais algos

**troumad** · 12/06/2005, 18h33

Envoyé par javatwister

mort de rire, t'as raison, j'en oublie le 2

et mis le 1 en trop !
Sur ton PC, le tien prend 160 et le mien ?

**Celelibi** · 12/06/2005, 18h36

J'obtiens en moyenne 73ms quand je monte à 10000.
Le code de JT mets plus de 2 secondes en moyenne.
Et le tien troumad : 105ms en moyenne.

Hey, mon code est pas le plus court, mais il semble être le plus rapide (du moins sur ma machine).
J'aurais pourtant cru que la méthode du crible d'Eratosthène aurait été plus rapide.
Remarque, dans ma boucle principale je n'ai ni multiplication, ni division (2 opération assez lourdes).

Bon, avis aux amateurs, il doit sûrement y avoir moyen de faire encore plus rapide.

**javatwister** · 12/06/2005, 18h39

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
<script type="text/javascript"> 
 
t1=new Date();
 
r=[2,3]
t=new Array()
 
for(i=3;i<10000;i+=2){
 
t[i]=i
 
for(j in t){
	if(i % j == 0) break
 
	if(j > i/j) {
		r.push(i)
		break
	}
}
 
}
 
t2=new Date();
 
alert("temps: " + (t2 - t1) + " ==> " + r.join(' '));
 
</script>

**javatwister** · 12/06/2005, 18h46

hum... va falloir régler nos montres là

**Celelibi** · 12/06/2005, 18h57

JT, y'a rien à faire, ton script mets toujours plus de 2 secondes pour s'exécuter sur mon pc.
Mon CPU est un AMD Athlon 1.1GHz utilisé à 94% par seti@home.

[edit]
'tain JT tu fous quoi ?
En remplaçant ton for (j in t) par un for (j=0; j<t.length; j++) tu passe de 2 secondes à 110ms.

note : ces résultats sont obtenus avec firefox linux.
[/edit]