Factorisation en nombres premiers

Soyez le premier à donner votre avis sur cette source.

Snippet vu 15 219 fois - Téléchargée 30 fois

Commenter

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.

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

Ajouter un commentaire

Commentaires

Signaler
yacouyahaya
Messages postés
3
Date d'inscription
mercredi 19 mars 2008
Statut
Membre
Dernière intervention
6 juin 2010
 -
salut les mecs, je suis un débutant mais pas un debutant en tant que tel car jais des serieux problemes en algorithme essayer de m'aider afin que je puisse un jour poster ne ce reste qu'un petit code pour qu'en fin je me sente programmeur je vous pris de m'aider les amis merci
Signaler
jean_marc_n2
Messages postés
170
Date d'inscription
jeudi 11 décembre 2003
Statut
Membre
Dernière intervention
24 janvier 2009
 -
oui c'est exact le elseif k=3 est inutile.

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 :-)
Signaler
us_30
Messages postés
2065
Date d'inscription
lundi 11 avril 2005
Statut
Membre
Dernière intervention
14 mars 2016
 8 -
Hum... Intéressant la petite formule de Jean_Marc_N2 : "d = 5 + ((k - 2) \ 2) * 2 + ((k - 3) \ 2) * 4" qui remplace la forme 6n-1 et 6n+1 . Je ne connaissais pas...

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.
Signaler
chewbaka62
Messages postés
67
Date d'inscription
mardi 1 novembre 2005
Statut
Membre
Dernière intervention
30 juillet 2006
 -
Pas de problème, Jean-Marc. Je suis tout à fait d'accord ( et c'est normal) de faire l'objet de critiques surtout quand elles viennent de connaisseurs. Je suis là pour apprendre après tout. Il y a juste la manière de le dire. Pour changer de sujet, j'ai examiné ton code et c'est vrai que ça n'a rien à voir avec ce que j'ai fait et je t'en remercie vivement.
A bientôt et sans rancune.
Chewbaka
Signaler
jean_marc_n2
Messages postés
170
Date d'inscription
jeudi 11 décembre 2003
Statut
Membre
Dernière intervention
24 janvier 2009
 -
Hello,
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 :-)
Afficher les 12 commentaires
S'inscrire maintenant

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.

Du même auteur (chewbaka62)