Sujet Précédent Sujet Suivant

NOMBRES PREMIERS

Bricomix Messages postés 340 Date d'inscription vendredi 11 octobre 2002 Statut Membre Dernière intervention 14 février 2005 - 8 déc. 2002 à 20:42
cs_Julien39 Messages postés 6414 Date d'inscription mardi 8 mars 2005 Statut Modérateur Dernière intervention 29 juillet 2020 - 6 mai 2006 à 10:06

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/5286-nombres-premiers

cs_Julien39 Messages postés 6414 Date d'inscription mardi 8 mars 2005 Statut Modérateur Dernière intervention 29 juillet 2020 371
6 mai 2006 à 10:06

Beaucoup de maladresses pour le calcul, la boucle while peut aisément être remplacée par une for, le code est illisible, non commenté et tu n'utilise aucune des optimisations possibles.
5/10 parce qu'il fonctionne et pour le calcul du temps

Baffff Messages postés 5 Date d'inscription mardi 10 décembre 2002 Statut Membre Dernière intervention 24 février 2004
11 déc. 2002 à 19:03

Vi, j'ai fait à peu près le meme dans le train c't'aprèm (je l'ai pas sous les yeux), on peut aussi commencer avec x = 2 pour éviter de tester la division par 2 pour chaque nombre
(en modifaint 2 ou 3 trucs)

Bricomix Messages postés 340 Date d'inscription vendredi 11 octobre 2002 Statut Membre Dernière intervention 14 février 2005
11 déc. 2002 à 15:33

En faites je me suis complètement trompé, alors je l'ai remodifié, et voilà le nouveau code (environ 5% plus rapide que l'original) ... voilà le nouveau code :

Dim a As Long, n As Long, x As Long, y As Double

ReDim t(nbr + 2)

a = 3 'on demarre direct en testant 3
n = 1
y = 2 'sera la racine carrée du nombre à tester
t(1) = 2

While n <= nbr
x = 1
While x <= n And t(x) < y
If a Mod t(x) = 0 Then GoTo NFirst
x = x + 1
Wend
n = n + 1
t(n) = a
NFirst:
a = a + 2
y = Sqr(a + 1)
Wend

Baffff Messages postés 5 Date d'inscription mardi 10 décembre 2002 Statut Membre Dernière intervention 24 février 2004
10 déc. 2002 à 23:48

Heu, Bricomix, au fait, vérifie quand même car ça marche jusqu'à 7, après il me trouve que 9 est un nb premier, y'a un binz....
J'ai pas le temps de coder pour l'instant, je regarde demain.

Baffff Messages postés 5 Date d'inscription mardi 10 décembre 2002 Statut Membre Dernière intervention 24 février 2004
10 déc. 2002 à 21:09

Vi, j'ai bien pensé à un truc comme ça, mais en bon étudiant modèle, on m'a dit d'éviter les GOTO, alors, j'évitais les GOTO. Ceci dit effectivement c'est 2 fois plus rapide. Par contre, je peux pas changer la source, y faut que je recrée un compte à chaque fois que je veux me connecter, comprend pas... Mon login va finir par être long :-). Merci à tous pour votre aide
A+

Bricomix Messages postés 340 Date d'inscription vendredi 11 octobre 2002 Statut Membre Dernière intervention 14 février 2005
10 déc. 2002 à 19:36

Pour Baff, efface tout ce qu'il y a dans la procédure sub "calcul" et mets-ça, c'est 2 fois plus rapide (mon athlon a 1150MHz a fait - de 23 secondes les 1 millions, au lieu de 43 au départ !!!) :

Dim a As Long, n As Long, x As Long, y As Double

ReDim t(nbr + 2)

a = 3 'on demarre direct en testant 3
n = 1
y = 2 'sera la racine carrée du nombre à tester
t(1) = 2

While n <= nbr
x = 1
If n Mod 2 0 Or n Mod 5 0 Then GoTo LTomber
While x <= n And t(x) < y
If a Mod t(x) = 0 Then GoTo NFirst
x = x + 1
Wend
LTomber:
n = n + 1
t(n) = a
NFirst:
a = a + 2
y = Sqr(a + 1)
Wend

TheBabyCool Messages postés 34 Date d'inscription dimanche 2 septembre 2001 Statut Membre Dernière intervention 4 mars 2003
9 déc. 2002 à 23:12

Mais très bien quand meme

TheBabyCool Messages postés 34 Date d'inscription dimanche 2 septembre 2001 Statut Membre Dernière intervention 4 mars 2003
9 déc. 2002 à 23:12

moi j'ai fait un autre algo qui arrive a env. 1million en moin de 20s sur mon p2 400mhz.

Proger Messages postés 248 Date d'inscription vendredi 10 novembre 2000 Statut Membre Dernière intervention 19 décembre 2008
9 déc. 2002 à 18:33

Bon, Baff², indice : utilise GoTo pour remplacer le booleen. Je sais, c'est "sale", mais c'est rapide. Par la même occasion tu te débarasse des tests superflu (y'en a!) et tu réduit à une ligne le test a mod t(x) = 0 then goto ... tu gagnes 5% de vitesse. vala :) à vot' service msieur dame.
ps : j'aime bien les artefacts que tu utilises pour optimiser le code, mais tu en a oublié 1 : tout chiffre se terminant par 5 n'est pas premier, donc, en plaçant judicieusement un "mod 5 = 0" tu peux encore grapillé.

cs_Bafff Messages postés 1 Date d'inscription lundi 9 décembre 2002 Statut Membre Dernière intervention 9 décembre 2002
9 déc. 2002 à 14:23

Merci Proger pour le code, justement je galérais la-dessus, en plus, mon login baff marche pus, j'ai dû rajouter un "f". Je cherche pour virer le booleen, mais c'est pas concluant pour l'instant, je perd du temps.
Vbsupernul, pour le seti@home c'est vrai qu'il faudrait accélérer un peu les calculs.
Et en ce qui concerne le cryptage, y'a des gens bien plus calés qui cherchent depuis longtemps, et qui doivent rigoler en voyant mon code. Merci pour l'aide et les commentaires, ça motive tout plein....

Proger Messages postés 248 Date d'inscription vendredi 10 novembre 2000 Statut Membre Dernière intervention 19 décembre 2008
9 déc. 2002 à 13:28

Le chrono précis :
dans le sub command_click :
t1! = Timer
Call calcul(NbrMax, t())
t2! = Timer
label.caption = (t2! - t1!) * 1000 & " ms"

ronanry Messages postés 190 Date d'inscription lundi 25 novembre 2002 Statut Membre Dernière intervention 22 décembre 2009
9 déc. 2002 à 10:16

si ton code est si bien que ca...(j'ai aps encore regarder :-p (honte a moi))
bref si c si bien... les clefs publiques (je parle niveau cryptage la) ont du souci a se faire...

Proger Messages postés 248 Date d'inscription vendredi 10 novembre 2000 Statut Membre Dernière intervention 19 décembre 2008
9 déc. 2002 à 10:00

Ce qui est impressionant c'est surtout la vitesse via interpréteur de code (mode création de vb) et la vitesse de l'exécutable compilé en code natif :
- 1700 ms en interpreteur
- 230 ms en exe natif.
(j'ai ajouter un chti chrono bien sûr pour avoir ces resultats)
mais on peux mieux faire encore ! en se débarassant de la booleenne "erreur" on gagne quelques ms (je te laisse trouver comment)

Vbsupernul Messages postés 287 Date d'inscription vendredi 25 octobre 2002 Statut Membre Dernière intervention 18 janvier 2004
9 déc. 2002 à 08:33

Lol, à quand la ^m chose pour faire avancer seti@home + vite ? :D

Vbsupernul Messages postés 287 Date d'inscription vendredi 25 octobre 2002 Statut Membre Dernière intervention 18 janvier 2004
9 déc. 2002 à 08:26

12 secondes pour 500000...
C vraiment super rapide

cs_Baff Messages postés 3 Date d'inscription dimanche 8 décembre 2002 Statut Membre Dernière intervention 8 décembre 2002
8 déc. 2002 à 23:01

D'ailleurs ça y est, je me suis servi d'un code posté par Popi (merci à lui :-) ) pour les calculs sur les heures, le zip est mis à jour.

cs_Baff Messages postés 3 Date d'inscription dimanche 8 décembre 2002 Statut Membre Dernière intervention 8 décembre 2002
8 déc. 2002 à 21:52

Ok, je vais essayer pour le chrono, mais si ça doit ralentir, j'vois pas bien l'intérêt... Faut ruser p'têt... Mais ça risque de prendre un peu de temps, c'est vrai que je débute. Merci pour les conseils.
A+

cs_tex Messages postés 116 Date d'inscription lundi 16 septembre 2002 Statut Membre Dernière intervention 23 mai 2004
8 déc. 2002 à 21:32

...y en a qu'on la bosse des maths en ce moment sur vbfrance :-)

Vbsupernul Messages postés 287 Date d'inscription vendredi 25 octobre 2002 Statut Membre Dernière intervention 18 janvier 2004
8 déc. 2002 à 21:25

Ouè, ben qd même, essaie de rajouter un chrono, parcke j'ai essayé mais le chrono bouge pas, toute la mémoire est captée par le calcul...

cs_Baff Messages postés 3 Date d'inscription dimanche 8 décembre 2002 Statut Membre Dernière intervention 8 décembre 2002
8 déc. 2002 à 21:22

Merci beaucoup, j'suis flatté !
Je me suis bien creusé les méninges aussi faut dire.

Vbsupernul Messages postés 287 Date d'inscription vendredi 25 octobre 2002 Statut Membre Dernière intervention 18 janvier 2004
8 déc. 2002 à 21:12

Super le prog:
Pentium 4 à 1695 Mhz, moins de 23 secondes pour trouver UN MILLION de nombres premiers...
Y faudrait juste rajouter un chronomètre ;)
10/10!!!

Bricomix Messages postés 340 Date d'inscription vendredi 11 octobre 2002 Statut Membre Dernière intervention 14 février 2005
8 déc. 2002 à 20:42

Ben sur mon Athlon XP1800+ (euh, j'ai un petit problême avec ma carte mère, donc il est qu'a 1150Mhz au lieu de 1500MHz), j'ai fait 16 secondes pour les 500000. En tout cas c'est bien, j'en avais fait un beaucoup plus beau, mais 10x moins rapide. Très bon code (un petit peu tordu quand même) : 9/10

Discussions similaires

Nombre Premier

Traduction d'un nombre reel en chiffres en arabe

convertir chiffres romains en nombre arabe

Écrivez un programme Java (Premiers.java) qui permet d'afficher

decomposition d'un nombre en java

Votre réponse

Discussions similaires