DÉCOMPOSITION (JUDICIEUSE) EN FACTEURS PREMIERS
cs_Alain Proviste
Messages postés
908
Date d'inscription
jeudi 26 juillet 2001
Statut
Modérateur
Dernière intervention
1 février 2015
-
28 mars 2005 à 19:20
Cacophrene Messages postés 251 Date d'inscription lundi 29 mars 2004 Statut Membre Dernière intervention 4 mars 2008 - 2 mars 2010 à 11:58
Cacophrene Messages postés 251 Date d'inscription lundi 29 mars 2004 Statut Membre Dernière intervention 4 mars 2008 - 2 mars 2010 à 11:58
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/30392-decomposition-judicieuse-en-facteurs-premiers
https://codes-sources.commentcamarche.net/source/30392-decomposition-judicieuse-en-facteurs-premiers
2 mars 2010 à 11:58
Ce code a plus de 4 ans et, depuis plusieurs années, je ne pratique plus du tout Visual Basic. Je suis hélas désormais incapable de t'aider (pas d'IDE sous la main, souvenirs lointains de la syntaxe, etc.)...
Seule remarque : ce problème de fenêtre me paraît curieux. Le problème vient peut-être d'ailleurs... Vérifie bien ton code et la manière dont tu manipules les fenêtres.
Cordialement,
Cacophrène
2 mars 2010 à 09:37
J'etais à la recherche d'un petit programme pour la decomposition en facteurs premiers.
J'ai utilisé votre code du 14/05/2005 08:26:26 ( commentaire plus haut ), seul inconvenient la fonction ne se decharge pas. Si je veut decomposer un deuxieme nombre je dois totalement sortir de la forme que j'ai crée et y retourner de nouveau. Comment regler ce détail.
Ps : je suis en VBA sous excel ( la decomposition me sert dans une autre application )
15 mai 2005 à 10:49
Oui, le fonctionnement est différent. Sous VB, la valeur est conservée entre les appels.
Cordialement,
Cacophrène
14 mai 2005 à 22:11
Depuis la dernière fois, j'ai aussi repris mon code, et je l'ai amélioré en tenant compte de ta remarque... IL semble donc indépendament l'un de l'autre, on arrive quasiment au même résultat. La seule différence c'est que dans ton cas tu évite la répétition du test en passant par une fonction Diviser.
Par ailleurs, j'ai commis une petite erreur qui coûte du temps lorsqu'on tombe sur un grand nombre premier. La borne LOOP UNTIL peut-être arrêté à la racine carré du Nombre, soit Diviseur1 > Nombre^0.5
Un détail, sans conséquence, c'est les deux valeurs 6 * (Incrément - 1) - 1 et 6 * (Incrément - 1) + 1, qui pouraient aussi s'écrire sans parenthèse, soit 6 * Incrément - 7 et 6 * Incrément - 5.
Bon, dans mon cas j'utilise le VBA, il doit y avoir une différence de fonctionnement. En effet, si je comprends bien tu utilises la variable Chaîne pour inscrire au fur et à mesure la décomposition. Dans mon cas, cette variable est automatiquement remise vide à chaque appel...
Voilà, c'est tout ce que je pouvais dire... sinon je pense que globalement ton code est pas mal...
Bonne programmation,
Us.
14 mai 2005 à 08:26
J'ai réfléchi à tout ceci. Je te propose le code suivant, qui reprend ta source en utilisant par ailleurs ma fonction auxiliaire Diviser. Voici donc :
-----------------------------------------
Option Explicit
Dim Incrément As Long, Diviseur1 As Long, Diviseur2 As Long, Chaîne As String, I As Integer
Function Décomposer(Nombre As Double) As String
Do
Incrément = Incrément + 1
Select Case Incrément
Case 1
Diviseur1 = 2
Diviseur2 = 3
Case Else
Diviseur1 = 6 * (Incrément - 1) - 1
Diviseur2 = 6 * (Incrément - 1) + 1
End Select
Nombre = Diviser(Nombre, Diviseur1)
Nombre = Diviser(Nombre, Diviseur2)
Loop Until Diviseur1 > Nombre
Décomposer = Chaîne
End Function
Function Diviser(ByRef Nombre As Double, ByVal N As Double) As Long
I = 0
While Nombre Mod N = 0
I = I + 1
Nombre = Nombre / N
Wend
If I <> 0 Then
If Chaîne <> Empty Then Chaîne = Chaîne & " * "
If I 1 Then Chaîne Chaîne & N Else Chaîne = Chaîne & N & "^" & I
End If
Diviser = Nombre
End Function
-----------------------------------------
Qu'en penses-tu ?
Cordialement,
Cacophrène
8 mai 2005 à 17:08
Oui, c'est vrai ! IL faudrait améliorer ce point. Une idée ?
(J'ai déposé ce listing : http://www.vbfrance.com/code.aspx?ID=31149)
Autrement, j'ai pas grand à dire pour votre listing... Enfin... juste la fonction "Let" héritage d'un lointain passé, est falcultaive et pourait être omise... mais ne change rien au programme...
Amicalement,
Us.
8 mai 2005 à 11:57
Bon programme. Dommage seulement que 5 * 5 ne soit pas noté 5 ^ 2. Songe bien que 1024 donne, avec ta fonction 2*2*2*2*2*2*2*2*2*2 et non pas 2 ^ 10, qui est tout de même plus agréable à lire. Mais sinon, rien à dire.
Cordialement,
Cacophrène
1 mai 2005 à 22:43
Votre remarque sur la forme des nombres premiers m'a inspiré... J'ai réutilisé votre idée sous la forme 6p-1 et 6p+1 (=même chose), mais j'ai écris une fonction plus courte et semble-t-il plus rapide...
Voici le listing :
=
Function Decompose(A As Double) As String
'Traitement A en entier positif
A = Abs(Int(A))
Do
'nbop = nbop + 1 ' correspond de boucle
t = t + 1
Select Case t
Case 1
N = 2
N2 = 3
Case Else
N = 6 * (t - 1) - 1
N2 = 6 * (t - 1) + 1
End Select
If A Mod N = 0 Then
Decompose = Decompose & Trim(Str(N)) & "*"
A = A / N
If t > 1 Then t t - 1 Else t 0
GoTo suite
End If
If A Mod N2 = 0 Then
Decompose = Decompose & Trim(Str(N2)) & "*"
A = A / N2
If t > 1 Then t t - 1 Else t 0
End If
suite:
Loop Until N > A
'MsgBox nbop
Decompose = Left(Decompose, Len(Decompose) - 1) 'enlève le dernier signe *
End Function
=
Pour 1346592975, le nombre d'opérations (ou de boucle dans mon cas) et de 179... sa décomposition vaut : 3*5*5*7*13*191*1033
Le temps est trop court pour être mesuré...
Voilà, comme quoi, une idée bien exprimée peut aider...
Merçi, donc...
=
Us.
2 avril 2005 à 13:29
Ce que tu proposes pour la fonction 2/4 change peu l'ensemble, elle n'est pas vraiment plus simple et cela n'a pas d'importance (encore une fois, parce que l'algorithme est destiné à des valeurs Long).
Enfin, comme le remarque Saros, charger une liste de nombres premiers demande de la mémoire (plus que le code seul).
Ceci dit :
J'aurais pu utiliser la formule dérivée du théorème de Wilson : pour n > 1, les nombres premiers sont f(n) = 2 + (2n! mod n + 1). Mais l'approximation de la factorielle donnée par Stirling montre que les valeurs prises sont rapidement très grandes, donc : solution écartée.
Pour les grands entiers, il y a bien sûr des techniques puissantes, mais que mon niveau en VB ne me permet pas de traduire, comme les algorithmes de Pollard, la factorisation en courbe elliptique de Lenstra ou même, le plus puissant connu : le crible spécial de corps de nombres (SNFS).
En fait, j'ai présenté ce que je sais programmer, en notant que c'était plus efficace que pas mal de codes présents sur ce site. Mais ce n'est pas un algorithme destiné à de grands nombres (Long ne le permet pas) ou à battre un record de vitesse :-)
Quant au jugement sur la réflexion présente et insuffisante, cela n'engage que toi...
Cacophrène
29 mars 2005 à 20:45
Enfin c'est à voir...
29 mars 2005 à 19:03
29 mars 2005 à 18:57
Pour reprendre ta fonction 2/4 en plus simple :
- soit N 5 et J 2
- N N + J, donc N 7
- J 6 - J, donc J 4
et ainsi de suite :)
Pour les facteurs premiers, j'ai pas bien regardé, mais dis toi bien que pour un nombre un peu élevé, les nombres premiers deviennent bien rares... Pourquoi ne pas charger un fichier qui les contient ? Ca evite des calculs et on trouve facilement ce genre de liste sur internet... ^^
Bon courage quand même, on voit qu'il y a eu de la réflexion... mais pas assez ! ;oP
28 mars 2005 à 19:20