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

Version imprimable

Voir 40 message(s) de cette discussion en une page

12/06/2005, 10h21
javatwister

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

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() :wink:

ps: et non, je ne me suis pas converti aux mathématiques; là c'est juste de la détente :P
12/06/2005, 10h25
troumad

Regarde ma page : http://troumad.free.fr/Math/nb_premiers.php
12/06/2005, 10h30
javatwister

salut :)

Citation:

Envoyé par troumad

Regarde ma page

euh... oui;

et alors?
12/06/2005, 10h33
troumad

Citation:

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 :) .
12/06/2005, 10h48
javatwister

hum;

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

:arrow: inciter à la mise en oeuvre de javascript dans des objectifs variés;
:arrow: développer la curiosité, l'envie de découvrir et d'inventer chez les jeunes adeptes;
:arrow: s''habituer à respecter des contraintes de fond ou de forme dans la création javascript / html
:arrow: développer la lecture / compréhension de code (voir premiers défis)
:arrow: 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 :wink:
:arrow: finalement, donner la possibilité à tout le monde d'évoluer dans sa manière de coder, quel que soit son niveau;

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

:arrow: 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é.

:arrow: Enfin, ici, on n'utilise que les pouvoirs ridiculement modestes de javascript pour arriver à ses fins.
12/06/2005, 10h56
troumad

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 !
12/06/2005, 12h11
javatwister

très joli 8O

tu peux le mettre en clair ici?

bon, le défi est lancé!

Code:

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 ?

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

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:

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

12/06/2005, 16h19
troumad

Citation:

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 !

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

zarbi, isn't it?

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

12/06/2005, 17h36
Celelibi

Citation:

Envoyé par troumad

Citation:

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 :P)
12/06/2005, 18h13
troumad

Citation:

Envoyé par javatwister

r="1 3"

Les deux premiers nombres premiers sont 2 et 3 :(

Citation:

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.

Citation:

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 :P)

Tu as testé le mien ? Je monte à 10000 comme javatwister
12/06/2005, 18h32
javatwister

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

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 :roll:
12/06/2005, 18h33
troumad

Citation:

Envoyé par javatwister

:lol: 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 ?
12/06/2005, 18h36
Celelibi

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

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

12/06/2005, 18h46
javatwister

hum... va falloir régler nos montres là :roll:
12/06/2005, 18h57
Celelibi

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

[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. :P
note : ces résultats sont obtenus avec firefox linux.
[/edit]
12/06/2005, 19h11
javatwister

bah, chez moi, le gain est invisible!

alors que ton premier script plantait presque avec un max à 10000 8O

Voir 40 message(s) de cette discussion en une page