Version imprimable
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 ?
3.2 GHz sous Windows avec Ffx et IE (le 1er un peu plus lent)
Et avec ta bête de course ça donne quel temps pour nos 3 scripts ?
1) pour vos différents codes, je crainds que la division soit beaucoup plus lente qu'une multiplicationCitation:
Envoyé par javatwister
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
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.
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. :D
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. :)
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 ;)Citation:
Envoyé par Celelibi
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é 8O
L'aspi râle car la spirale m'inspire pas ... (j'étais pas inspiré)
faut être mathématicien pour appeler ça une spirale !
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.
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 :lol:
Le meme principe (crible d'Era...) peut se faire en beaucoup moins d'opération que ça.... Don cen théorie bien plus vite:Citation:
Envoyé par troumad
Y'a encore moyen de réduire dans la troisième boucle, mais c'est plus compliqué....Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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) :P
(et c'est troumad qui a eut son agreg ? :roll:)
Ya un moyen tres simple d'optimiser la derniere boucle qui consiste a faire un maximum d'additions au lieu de multiplications...
Copier-coller :
[edit] autre optimisation : inverser le test dans le vecteur et ne pas l'initialiser [/edit]Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
je m'étais jamais aperçu qu'on était cernés par les matheux ici :lol:
bref, promis, plus aucun défi mathématique jusqu'à la fin de mes jours;
Bah tu sais JT les math et l'informatique (en particulier la programmation) sont assez liés. :)
Pourquoi ? C'est si existant et intelletuellement jouissif ;)Citation:
Envoyé par javatwister
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é).
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...Citation:
Envoyé par javatwister
Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Deux remarques:Citation:
Envoyé par fred777888999
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 ?
il suffit d'utiliser explicitement des décalages binaires et on gagne quelques ms. :)
Je crois que cette fois on ne peut pas faire mieux. :)Code:
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
note : le même algo en C tourne en 0.18ms en moyenne. :)