FACTORISATION EN NOMBRES PREMIERS
us_30
Messages postés
2065
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
-
7 avril 2006 à 23:25
yacouyahaya Messages postés 3 Date d'inscription mercredi 19 mars 2008 Statut Membre Dernière intervention 6 juin 2010 - 24 juil. 2009 à 00:20
yacouyahaya Messages postés 3 Date d'inscription mercredi 19 mars 2008 Statut Membre Dernière intervention 6 juin 2010 - 24 juil. 2009 à 00:20
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/36954-factorisation-en-nombres-premiers
https://codes-sources.commentcamarche.net/source/36954-factorisation-en-nombres-premiers
24 juil. 2009 à 00:20
10 avril 2006 à 22:18
En fait c'est tout simple, on fait 2, 3, 5, puis on ajoute alternativement 2, 4, 2, 4, etc. Ca ne génère pas trop de nombres non premiers. On peut améliorer en éliminant les multiples de 7 assez facilement, puis les nombres de la forme 30m+5. Bien sur, dans une implémentation un peu plus sérieuse, on peut améliorer tout ça en pré-générant les d(k) pour les 1000 ou 10000 premiers nombres premiers, ce qui permet de faire un lookup plus rapide que le calcul, et avant de trouver un nombre premier dont le premier facteur est plus grand que le 10.000 nombre premier, il faut déjà un très grand nombre :-)
10 avril 2006 à 21:40
Juste une petite remarque en passant, dans la function d() les deux lignes :
ElseIf k = 3 Then
d = 5
sont inutiles, puisque la formule donne le bon résultat pour le cas où k=3, mais bon...
Amicalement,
Us.
10 avril 2006 à 16:42
A bientôt et sans rancune.
Chewbaka
10 avril 2006 à 13:50
je ne voulais pas être agressif, si je l'ai été je te prie de bien vouloir m'en excuser.
Je voulais simplement signaler qu'en règle générale, on ne résoud pas un problème de performances par un bricolage du langage, mais par l'utilisation d'algorithmes ou de structures de données plus efficaces.
L'algorithme que je propose peut être employé pour des nombres de toute taille, il suffit de regarder comment il fonctionne. Il est seulement limité par ce que le langage (ici VB) sait représenter en interne.
Bonne continuation :-)
10 avril 2006 à 10:40
10 avril 2006 à 09:38
Le programme d'exemple de Jean_Marc_N2 ne demande pas une maitrise du VB (addition, multiplication, division, modulo ah oui et un do while, compliqué le do while), simplement il faut s'y connaître en maths !!!
chewbaka62: si tu connais autant de théorèmes (qui me sont totalement inconnus), pourquoi implémenter la version la plus lente qui soit au lieu de (je cite) la version eliptique, de fermat, mersenne ?
et surtout pourquoi demander "comment gagner en rapidité"...
Pas très logique tout ça.
Franchement si j'étudiais toutes sortes de tri de tableau (tri indexé, tri par liste chaînées, tri radix..) il ne me viendrait pas à l'esprit de coder un tri bulle.
9 avril 2006 à 22:50
Merci et à plus...
9 avril 2006 à 21:18
pour la rapidité il faut surtout employer un algorithme correct (ce n'est pas le cas de celui-ci).
Celui que je donne ici en exemple (pourtant trivial) retourne la décomposition en qq millisecondes, pour des nombres jusqu'à 2,147,483,647 (c'est la limite d'un long en VB) mais ce serait pareil même pour des nombres beaucoup plus grands.
Il est des milliers de fois plus rapide que le tien, et surtout n'est pas limité en taille (les nombres peuvent être aussi grands que l'on veut). Lire un peu sur le sujet peut être utile avant de proposer une implémentation d'un algorithme mathématique, et dans le cas présent (décomposition en facteurs premiers), le problème est à l'étude depuis l'an -250... La littérature sur le sujet est, comment dire ... abondante :-)
Voici une implémentation non optimisée de la méthode "Factorisation par division". On est loin des performances qu'on peut obtenir avec les courbes elliptiques par exemple, mais on peut déjà factoriser des nombres ayant une petite dizaine de chiffres, sans problème.
'
' retourne dans s la decomposition en fateurs premiers
'
Private Function factor(nbre As Long, s As String) As Boolean
Dim n As Long, k As Long, dk As Long
Dim t As Long, q As Long, r As Long
n nbre: t 0: k = 0
Do While n <> 1
dk = d(k + 1)
q = n \ dk
r = n Mod dk
If r = 0 Then
' ici on pourrait grouper les dk si identiques
s = s & dk & " "
n = q
Else
If q > dk Then
k = k + 1
Else
s = s & n & " "
Exit Do
End If
End If
Loop
End Function
Public Function d(ByVal k As Long) As Long
If k = 1 Then
d = 2
ElseIf k = 2 Then
d = 3
ElseIf k = 3 Then
d = 5
Else
d = 5 + ((k - 2) \ 2) * 2 + ((k - 3) \ 2) * 4
End If
End Function
9 avril 2006 à 14:20
Je m'en vais essayer cela dès que j'aurai un peu de temps.
Merci également à US pour son site, véritable mine à sources.
Chewbaka
9 avril 2006 à 11:01
Private Sub mnuFichierFactor_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles mnuFichierFactor.Click
Dim tFactorize as new threading.thread
tFactorize.Start()
End Sub
Voilà ! Je pense que cela ira plus vite.
Redman
7 avril 2006 à 23:25
Pour gagner en rapidité, il suffit de programmer le crible d'erasthostène... puis d'utiliser un test avec les nb premiers... seul inconviénient, la mémoire... mais il y a de la marge avec le matériel de nos jours...
Sans vouloir en profiter ici, je pense que dans mon modeste site tu trouveras quelques pistes ou source d'inspiration... dont d'ailleurs certaines ont été exposées sur ce site à la critique...
Amicalement,
Us.