TROUVEZ LA LISTE DES NOMBRES PREMIERS TRES RAPIDEMENT !
cs_Sophus
Messages postés37Date d'inscriptionmercredi 20 novembre 2002StatutMembreDernière intervention27 juillet 2007
-
24 nov. 2002 à 16:28
cs_astra
Messages postés21Date d'inscriptionsamedi 21 décembre 2002StatutMembreDernière intervention19 mars 2004
-
9 mai 2003 à 20:11
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
cs_astra
Messages postés21Date d'inscriptionsamedi 21 décembre 2002StatutMembreDernière intervention19 mars 2004 9 mai 2003 à 20:11
c po pour etre mechant mais le mien il met 1.81s sur un Athlon 900mhz pour jusqu'à 220217... à vous de juger...
je fe po de la pub pour le mien mais celui ci est TRES LENT :)
cs_Zeroc00l
Messages postés367Date d'inscriptionlundi 1 avril 2002StatutMembreDernière intervention11 février 2010 27 nov. 2002 à 16:30
(ben j'ai bien le droit de faire un peu de pub now !!! :p :) )
cs_Zeroc00l
Messages postés367Date d'inscriptionlundi 1 avril 2002StatutMembreDernière intervention11 février 2010 27 nov. 2002 à 13:24
Salut je suis en Ts Spé maths. Et j'ai eu a faire un petit prog qui decompose de grand nombre en facteur premier. Etant donne que le prog tournait sous Ti 83+, fallait pas etre presse. Je l'ai donc optimise a fond ( d'apres mes connaissance actuel). Voila ce que cela donne, traduit en langage vb, en utilisant les mëmes variables que toi.Rajoute un label ( name : label4 ), supprime tout ton code et met celui la :
Dim div, nbr, nbrdiv As Long
Dim Lst() As Long
Private Sub Text1_KeyPress(KeyAscii As Integer)
If KeyAscii < 48 And KeyAscii <> 8 Or KeyAscii > 57 Then KeyAscii = 0
End Sub
Private Sub Command1_Click()
'Initialisation : on rappelle que 1 n'est pas consideré comme un nombre premier
If nbr < 2 Then MsgBox "Quel utilité de calculer ? "
Text1.Locked = True
Command1.Enabled = False
'Le Caption du label3 sera toujours égale a "En Travail :"
'Un autre label ( le 4) indiquera à droite du label3 le nombre
'Ca évitera au pc d'avoir a rajouter a chaque fois "En travail :"
Label3.Caption = "En travail : Test du diviseur :"
While div <= Sqr(nbr) 'Rajouter Int() ralenti t'il le test ? Mais sans Int() le test s'effectue sur des nombre de type single... ce qui ralenti ) A voir ...
Label4.Caption = div & " sur " & Int(Sqr(nbr))
'Plusieurs possiblités :
' --> If nbr/div =int(nbr/div) Then
' --> If nbr mod div Then
' --> If nbr-(nbrdiv)*div Then
If nbr / div = Int(nbr / div) Then
Lst(nbrdiv) = div
nbrdiv = nbrdiv + 1
ReDim Preserve Lst(nbrdiv)
nbr = nbr / div
div = div - 1 ' si nbr multiple de 4 ? il faut retester "2"
End If ' On enleve donc 1 ...
div = div + 1 ' pour le rajouter la . resultat : aucun ( ou alors incremente )
DoEvents
Wend
If nbr Then
For div = 0 To nbrdiv - 1
Text2 = Text2 & Lst(div) & " * "
Next div
Text2 = Text2 & nbr
Else
MsgBox " Votre nombre est premier !"
End If
Text1.Locked = False
Command1.Enabled = True
Label3.Caption = "Factorisation terminée."
End Sub
Je l'ai testé, il marche assez rapidement.
Sinon pour ce qui est de la liste des nombre premier, l'algo de Proger est pas mal, mais sa boucle for ralentie encore le temps de calcul. Pk essayer de diviser par 8 si on sait que le nombre a tester n'ets pas divisible par 2 ?
Donc le mieux c'est carrement de tester els nombre premier inferieur a la racine carre du nombre :
Remplace :
For i = 3 To Int(Sqr(j)) + 1 Step 2
If j Mod i = 0 Then
Exit For
End If
Next i
If j Mod i <> 0 Then
Par :
i=0
Do
i=i+1
Until NPTable(i) > Int(Sqr(j)) Or not( j mod NPtable(i) )
If NPtable(i)>Int(Sqr(j)) Then
Et la suite...
J'en profite pour rapeler a Proger que 1 n'ets pas un nombre premeir. C'ets l'unité.
Voila, je pense que ca t'aidera ...
-={[ZeroCool]}=-
P.S. je vais mettre une source sur les nombres parfaits paires.
Proger
Messages postés248Date d'inscriptionvendredi 10 novembre 2000StatutMembreDernière intervention19 décembre 2008 26 nov. 2002 à 11:42
mic > 30 secondes pour calculer 220217 nombre premiers 30 secondes pour calculer jusqu'a 220217 (qui est premier) ?
car si c'est 30s pour arriver a 220217, c'est grave!
Il me faut 1,3 secondes avec un athlon 700Mo (slota) avec l'algo ci-dessous (5 sec avec l'affichage) :
Function FastNbPrems(MaxiVal As Long) As Long
'calcul tout les nombres premiers jusqu'a une valeur approchant de maxival
'intialisation
Dim NPtable() As Long, NPavance As Long
Dim i As Long, j As Long
ReDim NPtable(0 To 1) As Long
NPtable(0) = 1
NPtable(1) = 3
NPavance = 1
j = 3
'calcul
Do
j = j + 2
For i = 3 To Int(Sqr(j)) + 1 Step 2
If j Mod i = 0 Then
Exit For
End If
Next i
If j Mod i <> 0 Then
NPavance = NPavance + 1
ReDim Preserve NPtable(0 To NPavance)
NPtable(NPavance) = j
'Label1.Caption = j: DoEvents 'ralenti le calcul!
End If
Loop Until j >= MaxiVal
FastNbPrems = NPtable(NPavance)
End Function
(code home-made)
bon en fait le problème du code a Sophus est d'utiliser le disque dur plutôt que la ram pour sauvegarder les valeurs, sinon la théorie est bonne...
Il devrai sauvegarder la liste uniquement à la suspention/reprise du calcul.
cs_mic
Messages postés77Date d'inscriptionmardi 5 février 2002StatutMembreDernière intervention19 septembre 2012 25 nov. 2002 à 17:46
Non plus rapide pas besoin, ça va déja très vite, le temps qu'il aurait fallu à archimède pr les calculer. Seulement le truc serait de la garder aussi rapide en le rendant plus éfficace. J'ai un athlon 1800+, j'ai laissé tourner ton prg 30s, je suis arrivé à 220217 et il a réussi à me déclencher la sonnerie qui indique que le processeur est un peu trop utilisé. Je crois que c'est surtout sur ce point qu'il y a des choses à revoir, sinon on va tous être obligé de passer à l'itanium. Sinon je trouve que ton prog est très bien, et je trouve super qu'il y est de plus en plus de geans sur ce site qui se penche sur des applications scientifiques (maths, electroniques...) ezt tout ce que ça implique (pb avec le processeur). c'est quand même mieux que le carnet d'adresse. Après tout, c'est la base de l'informatique. Comme il disent chez google, mieux vaux un bon algorithme, qu'un tas de pub. Bon donc essaye de revoir pr le processeur (faudrait que ça dépende du processeur que tu as). Voila c'est tout. Je te met une bonne note. Bonne prog et bon maths.
cs_Sophus
Messages postés37Date d'inscriptionmercredi 20 novembre 2002StatutMembreDernière intervention27 juillet 2007 24 nov. 2002 à 18:21
Je sais je suis abonné à Science et Vie j'essaie justement d'étudier ca !
lol
bratislaprog
Messages postés23Date d'inscriptionmercredi 1 mai 2002StatutMembreDernière intervention24 novembre 2002 24 nov. 2002 à 17:04
Dans le science et vie du moi de novembre, il y a un article sur 3 indiens qui viennent de réaliser le programme le plus court (11 lignes, seulement) et le plus rapide pour trouver tous les nombres premiers. Ce prog est fondé sur de nouvelles propriétés, ils sont super fort, vas donc lire l'article, ça peut t'intéresser et leur méthode est bien plus rapide que celle que tu utilise (avec la racine carré) surtout pour les très très grands nombres.
Voilà
cs_Sophus
Messages postés37Date d'inscriptionmercredi 20 novembre 2002StatutMembreDernière intervention27 juillet 2007 24 nov. 2002 à 16:53
Voila la mise à jour!
cs_Sophus
Messages postés37Date d'inscriptionmercredi 20 novembre 2002StatutMembreDernière intervention27 juillet 2007 24 nov. 2002 à 16:49
Merci Pof je fais une ch'tite mise à jour de suite !
cs_Pof
Messages postés78Date d'inscriptionlundi 11 février 2002StatutMembreDernière intervention 7 février 20061 24 nov. 2002 à 16:44
petite ^précision : un nombre est premier si il n'a pas de diviseurs entre 2 et la racine carrée de ce nombre... ya encore moyen d'améliorer ton prog ^^
cs_Sophus
Messages postés37Date d'inscriptionmercredi 20 novembre 2002StatutMembreDernière intervention27 juillet 2007 24 nov. 2002 à 16:28
Voila j'ai mis le zip, laissez moi vos commentaires
9 mai 2003 à 20:11
je fe po de la pub pour le mien mais celui ci est TRES LENT :)
27 nov. 2002 à 16:30
> http://www.vbfrance.com/article.aspx?Val=6508
(ben j'ai bien le droit de faire un peu de pub now !!! :p :) )
27 nov. 2002 à 13:24
Dim div, nbr, nbrdiv As Long
Dim Lst() As Long
Private Sub Text1_KeyPress(KeyAscii As Integer)
If KeyAscii < 48 And KeyAscii <> 8 Or KeyAscii > 57 Then KeyAscii = 0
End Sub
Private Sub Command1_Click()
'Initialisation : on rappelle que 1 n'est pas consideré comme un nombre premier
ReDim Lst(0)
nbr = Val(Text1.Text)
div = 2
nbrdiv = 0
Text2.Text = ""
If nbr < 2 Then MsgBox "Quel utilité de calculer ? "
Text1.Locked = True
Command1.Enabled = False
'Le Caption du label3 sera toujours égale a "En Travail :"
'Un autre label ( le 4) indiquera à droite du label3 le nombre
'Ca évitera au pc d'avoir a rajouter a chaque fois "En travail :"
Label3.Caption = "En travail : Test du diviseur :"
While div <= Sqr(nbr) 'Rajouter Int() ralenti t'il le test ? Mais sans Int() le test s'effectue sur des nombre de type single... ce qui ralenti ) A voir ...
Label4.Caption = div & " sur " & Int(Sqr(nbr))
'Plusieurs possiblités :
' --> If nbr/div =int(nbr/div) Then
' --> If nbr mod div Then
' --> If nbr-(nbrdiv)*div Then
If nbr / div = Int(nbr / div) Then
Lst(nbrdiv) = div
nbrdiv = nbrdiv + 1
ReDim Preserve Lst(nbrdiv)
nbr = nbr / div
div = div - 1 ' si nbr multiple de 4 ? il faut retester "2"
End If ' On enleve donc 1 ...
div = div + 1 ' pour le rajouter la . resultat : aucun ( ou alors incremente )
DoEvents
Wend
If nbr Then
For div = 0 To nbrdiv - 1
Text2 = Text2 & Lst(div) & " * "
Next div
Text2 = Text2 & nbr
Else
MsgBox " Votre nombre est premier !"
End If
Text1.Locked = False
Command1.Enabled = True
Label3.Caption = "Factorisation terminée."
End Sub
Je l'ai testé, il marche assez rapidement.
Sinon pour ce qui est de la liste des nombre premier, l'algo de Proger est pas mal, mais sa boucle for ralentie encore le temps de calcul. Pk essayer de diviser par 8 si on sait que le nombre a tester n'ets pas divisible par 2 ?
Donc le mieux c'est carrement de tester els nombre premier inferieur a la racine carre du nombre :
Remplace :
For i = 3 To Int(Sqr(j)) + 1 Step 2
If j Mod i = 0 Then
Exit For
End If
Next i
If j Mod i <> 0 Then
Par :
i=0
Do
i=i+1
Until NPTable(i) > Int(Sqr(j)) Or not( j mod NPtable(i) )
If NPtable(i)>Int(Sqr(j)) Then
Et la suite...
J'en profite pour rapeler a Proger que 1 n'ets pas un nombre premeir. C'ets l'unité.
Voila, je pense que ca t'aidera ...
-={[ZeroCool]}=-
P.S. je vais mettre une source sur les nombres parfaits paires.
26 nov. 2002 à 11:42
car si c'est 30s pour arriver a 220217, c'est grave!
Il me faut 1,3 secondes avec un athlon 700Mo (slota) avec l'algo ci-dessous (5 sec avec l'affichage) :
Function FastNbPrems(MaxiVal As Long) As Long
'calcul tout les nombres premiers jusqu'a une valeur approchant de maxival
'intialisation
Dim NPtable() As Long, NPavance As Long
Dim i As Long, j As Long
ReDim NPtable(0 To 1) As Long
NPtable(0) = 1
NPtable(1) = 3
NPavance = 1
j = 3
'calcul
Do
j = j + 2
For i = 3 To Int(Sqr(j)) + 1 Step 2
If j Mod i = 0 Then
Exit For
End If
Next i
If j Mod i <> 0 Then
NPavance = NPavance + 1
ReDim Preserve NPtable(0 To NPavance)
NPtable(NPavance) = j
'Label1.Caption = j: DoEvents 'ralenti le calcul!
End If
Loop Until j >= MaxiVal
FastNbPrems = NPtable(NPavance)
End Function
(code home-made)
bon en fait le problème du code a Sophus est d'utiliser le disque dur plutôt que la ram pour sauvegarder les valeurs, sinon la théorie est bonne...
Il devrai sauvegarder la liste uniquement à la suspention/reprise du calcul.
25 nov. 2002 à 17:46
24 nov. 2002 à 18:21
lol
24 nov. 2002 à 17:04
Voilà
24 nov. 2002 à 16:53
24 nov. 2002 à 16:49
24 nov. 2002 à 16:44
24 nov. 2002 à 16:28