Discussion :

[Celelibi]

oui mon tout premier avant que je le modifie était un pure gros lourdo. :p
un if (i/j == parseInt(i/j)) pour vérifier la divisibilité, ça aide pas. En plus j'avais séparé en 2 fonctions par soucis de careté, mais ça rallentissait plus le script que ça le rendait lisible.

Donc voilà, après modifications ça me donne les résultats cités plus hauts.

Dis moi JT, tu test avec quel navigateur ? quel OS ? quel CPU ?

[javatwister]

3.2 GHz sous Windows avec Ffx et IE (le 1er un peu plus lent)

[Celelibi]

Et avec ta bête de course ça donne quel temps pour nos 3 scripts ?

[troumad]

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
[...]
for(i=3;i<10000;i+=2){
 
t[i]=i
 
[b]for(j in t)[/b]{
	if(i % j == 0) break
 
	if(j > i/j) {
		r.push(i)
		break
	}[...]

1) pour vos différents codes, je crainds que la division soit beaucoup plus lente qu'une multiplication
1) a) .(j > i/j) doit être moins rapide que .(j*j > i)
2) Si for(j in t)parcourt tous les i tel que t[ i ]=i (ceux qu'on a défini), il serait plus judicieux de placer le [i]t=i dans le if(j > i/j) pour ne tester par la suite que les nombres premiers

[zebuman]

Bonjour

j'interviens pour proposer un exercice intéressant pour découvrir les arcanes mystérieuses des nombres premiers.
L'exercice consiste à tracer un damier carré avec un nombre impair de cases. (de l'ordre de 51 cases de côté par exemple)
on affecte l'entier n à la case centrale, puis n+1, n+2... en tournant dans une spirale carrée, extrait:

n+4 n+3 n+2 n+11
n+5 [ n ] n+1 n+10
n+6 n+7 n+8 n+9

il s'agit de colorier en noir les cases où l'entier est premier, et en blanc les autres cases. On peut bien sûr intervertir des couleurs, voire choisir d'autres couleurs comme le vert, l'orange ou le rose fuschia.

et on obtient un résultat étrange, en commençant avec n=31 (à moins que ce soit 32, ou 33, je ne sais plus, c'est entre 30 et 40) , que je laisse découvrir à ceux qui voudront tenter l'expérience.

[Celelibi]

Dans mon livre de spé math (5 pages avant le crible d'Eratosthène) on a un carré de 25*25 centré sur le 41.
Juste pour information, ça s'appel la spirale d'Ulam.

Si vous voulez vous ammuser avec les nombres premiers, on peut aussi tracer la fonction p(x) qui a tout x associe le nombre d'entiers premiers inferieurs à cet x.

En s'éloignant un peu des nombres premiers, mais en restant dans le même domaine des mathématiques, on peut aussi chercher les premiers nombres parfaits.
rappel : un entier est dit parfait s'il est égal à la somme de ses diviseurs propres (autres que lui même).
exemples :
6 est divisible par 3, 2 et 1; 6 = 3+2+1
28 est divisible par 14, 7, 4, 2, 1; 28 = 14+7+4+2+1

le défi : en trouver un qui soit impair.

Enfin voilà c'était juste pour dire qu'avec les maths y'a de quoi s'ammuser.
Pour ceux qui aiment ça, je pense que Troumad (prof de math) doit avoir quelques bizzareries mathématiques qui trainnent dans ses archives.

[troumad]

Troumad (prof de math) doit avoir quelques bizzareries mathématiques qui trainnent dans ses archives.

C'est par erreur après une formation d'ingénieur en tout et en électronique que je me suis retrouvé en train de passer l'agreg de maths et en plus je n'ai eu ! Je n'ai pas de culture mathématique à vraiment dire. On m'a dit que j'ai resorti l'algo de je ne sais plus qui, j'en suis heureux ! Bien que je ne puisse pas le breveter et lui donner mon nom

[zebuman]

Merci Celelibi pour les précisions qui comblent ma mémoire défaillante.
Si vous voulez voir la spirale d'Ulam, http://zebujeux.free.fr/outerspace/s..._premiers.html

le script n'est pas vraiment optimisé

[SpaceFrog]

L'aspi râle car la spirale m'inspire pas ... (j'étais pas inspiré)
faut être mathématicien pour appeler ça une spirale !

[Celelibi]

La spirale est la façon d'enrouler les nombres lors de la construction de la grille. Même si elles est rectangulaire, ça n'en est pas moins une spirale.
Sinon, pour la diagonale, c'est bien une diagonale au sens mathématique du terme ; c'est à dire un segment de droite qui relie 2 sommets opposés d'un polygone.

[SpaceFrog]

pour la diagonale rien à redire elle est est bien diagonale ... pour l'enroulement ... ça confirmareait que le mathématiciens ne sont pas très manuels ... quand j'enroule mes tranches de jambon autour de mes endives ça à meilleure gueule que ça

[denisC]

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

Le meme principe (crible d'Era...) peut se faire en beaucoup moins d'opération que ça.... Don cen théorie bien plus vite:

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
 
function premiers()
{
 t=new Date()
 prem = new Array
 m = ceil(Math.sqrt(10000)); // = 100 :)
 for (i=3;i<=10000;i+=2)
  prem[i]=1;
 for (i=3;i<=m;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)
}

Y'a encore moyen de réduire dans la troisième boucle, mais c'est plus compliqué....

[Celelibi]

Ah mais oui, pourquoi j'ai pas vu.
C'est moi qui ait sorti la propriété qui dit que le premier nombre qu'on raye est n^2, donc forcément si y'a x nombres dans la grille, c'est pas la peine de tester plus loins que sqrt(x)


(et c'est troumad qui a eut son agreg ? )

[fred777888999]

Ya un moyen tres simple d'optimiser la derniere boucle qui consiste a faire un maximum d'additions au lieu de multiplications...
Copier-coller :

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

[edit] autre optimisation : inverser le test dans le vecteur et ne pas l'initialiser [/edit]

[javatwister]

je m'étais jamais aperçu qu'on était cernés par les matheux ici

bref, promis, plus aucun défi mathématique jusqu'à la fin de mes jours;

[Celelibi]

Bah tu sais JT les math et l'informatique (en particulier la programmation) sont assez liés.

[troumad]

je m'étais jamais aperçu qu'on était cernés par les matheux ici

bref, promis, plus aucun défi mathématique jusqu'à la fin de mes jours;

Pourquoi ? C'est si existant et intelletuellement jouissif

Pas mal pour le coup du m=10000^(1/2) (un gros oubli dans mon programme) et le k=2j (je n'y avais absolument pas pensé).

[fred777888999]

je m'étais jamais aperçu qu'on était cernés par les matheux ici

bref, promis, plus aucun défi mathématique jusqu'à la fin de mes jours;

Juste en homage a cette derniere phrase, une derniere petite optimisation bien inutile et pas forcement appropriée, ca depends vraiment de la qualite de l'interpreteur JS pour les entiers. Normalement, une multiplication par 4 est juste 1 double decallage et le calcul du carre de i est donc en theorie plus rapide comme ca...

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
 
function premiers() 
{ 
 t=new Date() 
 prem = new Array (10000)
 m =100;
 l=1;
 l1 = 1;
 for (i=3;i<=m;i+=2) {
 l2 = 4*i;
 l1 += l2 - 4;
 k=i*2;
  if (!prem[i]) { 
    for ( j=l1; j <= 10000; j+=k)
    prem[j]=1;
  }
 }
 t1=new Date() 
 s="temps : "+(t1-t)+"   " 
 for (i=3;i<=10000;i+=2) 
  if (!prem[i]) 
   s+=" "+i; 
 alert(s) 
}

[troumad]

[...]
l2 = 4*i;
l1 += l2 - 4;
[...]
if (!prem[ i ]) {
[..]

Deux remarques:
1) l1 += l2 - 4 car c'était le carré de i-2...
Et encore mieux (pas besoin d'une variable de plus) : l1+=4*i-4
2) if (!prem[ i ]) : mon réflexe de programmateur en C me signale que si on n'a pas définit prem[i] alors il vaut n'importe quoi. En javascript, il doit valoir faux ?

[Celelibi]

il suffit d'utiliser explicitement des décalages binaires et on gagne quelques ms.

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
function premiers()
{ 
t=new Date()
 prem = new Array (10000)
 m =100;
 l1 = 1;
 for (i=3;i<=m;i+=2) {
 l1 += (i<<2) - 4;
 k=i<<1;
  if (!prem[i]) {
    for ( j=l1; j <= 10000; j+=k)
    prem[j]=1;
  }
 }
 t1=new Date()
 s="temps : "+(t1-t)+"   "
 for (i=3;i<=10000;i+=2)
  if (!prem[i])
   s+=" "+i;
 alert(s)
}

Je crois que cette fois on ne peut pas faire mieux.

note : le même algo en C tourne en 0.18ms en moyenne.