Factorisation en nombres premiers
Soyez le premier à donner votre avis sur cette source.
Snippet vu 15 261 fois - Téléchargée 30 fois
Contenu du snippet
Programme permettant de factoriser des nombres composés jusqu'à 100000. J'ai voulu faire plus grand mais on perd en rapidité. Si vous pouviez mz dire ce qu'il faut faire pour gagner en rapidité sur des grands chiffres, n'hésitez pas.
Merci.
Merci.
Source / Exemple :
Private Sub mnuFichierFactor_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles mnuFichierFactor.Click
Dim intNbrePrem(100000) As System.Int32
Dim x, y, intNP As System.Int32
Dim intDiviseur, intFactor, intCompteurNP As System.Int32
Dim intNombre As System.Int32 = CInt(txtNombre.Text)
Dim strNombre, strFactor As System.String
intNbrePrem(0) = 2
intNbrePrem(1) = 3
intNP = 2
lblFactor.Text = ""
For x = 5 To 99999 Step 2
intDiviseur = 0
For y = 2 To Sqrt(x) Step 1
If x Mod y = 0 Then
intDiviseur += 1
End If
Next
If intDiviseur = 0 Then
intNbrePrem(intNP) = x
intNP += 1
End If
Next
For intCompteurNP = 0 To 9591 Step 1
intFactor = 0
strFactor = ""
Do While intNombre Mod intNbrePrem(intCompteurNP) = 0
intNombre -= intNombre / intNbrePrem(intCompteurNP)
intFactor += 1
strFactor = intNbrePrem(intCompteurNP) & "^" & intFactor & "."
Loop
lblFactor.Text &= strFactor
Next
End Sub
Private Sub MenuItem1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles MenuItem1.Click
txtNombre.Text = ""
lblFactor.Text = ""
End Sub
Private Sub mnuFichierQuitter_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles mnuFichierQuitter.Click
End
End Sub
A voir également
- Factorisation des nombres premiers
- Les nombres composés - Meilleures réponses
- Nombre premier et factorisation - Codes sources - C / C++ / C++.NET (Maths & Algorithmes)
- C / C++ / C++.NET : Factorisation d'un nombre en nombre premier - CodeS SourceS - Guide
- C / C++ / C++.NET : Factorisation d'un entier en produit de nombres premiers avec une fonction r&ea - Guide
- Nombre premier javascript - Guide
- Nombre premier python - Guide
Commentaires
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 :-)
- Messages postés
- 2065
- Date d'inscription
- lundi 11 avril 2005
- Statut
- Membre
- Dernière intervention
- 14 mars 2016
8Juste 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.
A bientôt et sans rancune.
Chewbaka
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 :-)
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.