[vb 8][.net 2]les diviseurs d'un nombre + nombres premiers (enumérator & testeur) + factorisation première + pgcd + ppcm

Soyez le premier à donner votre avis sur cette source.

Vue 13 712 fois - Téléchargée 457 fois

Description

Tout est dans le titre ;)

Bon ici pour des raisons de simplicité j'ai utilisé une list(Of Integer) pour les résultats.
Il est évident que si on veut encore gagner en rapidité, on doit passer par des array...
On peut aussi éviter Sort en mettant les div1 dans un array et les div2 dans un autre puis joindre les deux tableau (Div1[0]=>Div1[X] & Div2[X]=>Div2[0])

Enfin le résultat est la !
33 fois plus rapide à trouver les diviseurs de 2007 que la méthode classique !
A part pour 2 et 3 ou cela est plus long (à peine) - à cause de l'appel de List.Sort() -, le script prouve son efficacité !

Pour calculer des diviseurs de 15, ma méthode s'est avérée 1,5 fois plus rapide !

Juste à titre d'exemple, la recherche des diviseurs de 53612 prend 191 fois moins de temps avec ma méthode (326406 contre 62337475)
Celles des diviseurs de 100 mille : 230 fois plus rapide(514768 contre 118490968)

<EDIT()> _
Public Class Comment
'' La nouvelle version est en mode Windows et permet en plus tout ce qui est dit dans le titre ! (PGCD, PPCM, Factorisation première, ...)
'' De plus, les chiffres de rapidité décrit au dessus ne sont plus valide. La vitesse a été augmentée par deux pour les nombres pairs (et est restée inchanger pour les impairs)
End Class

Source / Exemple :


' ANCIEN CODE (Application Console, démontrer la puissance de getDivs, une nouvelle version encore plus rapide existe dans le ZIP)
Public Module MainModule

    Public Sub Main()
        On Error GoTo EndSub
        Do
            Console.Write("Entrez un nombre pour en connaître les diviseurs, N pour quitter: ")
            Dim Number As Integer = CInt(Console.ReadLine())
            Dim Diviseurs As List(Of Integer) = getDivs(Number)
            Console.Write("Le nombre que vous avez choisit a ")
            For I As Integer = 0 To Diviseurs.Count - 1
                Console.Write(Diviseurs(I) & IIf(I = Diviseurs.Count - 1, " ", ","))
            Next
            Console.WriteLine("pour diviseurs.")
            '' <TEST>
            Dim TimeWatcher As New Diagnostics.Stopwatch()
            TimeWatcher.Start()
            For X As Integer = 0 To 10000
                getDivs(Number)
            Next
            TimeWatcher.Stop()
            Console.WriteLine("La méthode que j'utilise :" & TimeWatcher.ElapsedTicks)
            TimeWatcher.Reset()
            TimeWatcher.start()
            For X As Integer = 0 To 10000
                getDivs_Bad(Number)
            Next
            TimeWatcher.Stop()
            Console.WriteLine("La méthode classique :" & TimeWatcher.ElapsedTicks)
            '' </TEST>
        Loop While True
EndSub:
    End Sub

    Public Function getDivs(ByVal Number As Integer) As List(Of Integer)
        getDivs = New List(Of Integer)
        Dim Div1 As Integer = 1
        Dim Div2 As Integer = Number
        While Div1 <= Div2
            If Div1 * Div2 = Number Then
                getDivs.Add(Div1)
                If Div1 <> Div2 Then getDivs.Add(Div2)
            End If
            Div1 += 1
            Div2 = Number \ Div1
        End While
        getDivs.Sort()
    End Function

    Public Function getDivs_Bad(ByVal Number As Integer) As List(Of Integer)
        Dim getDivs As New List(Of Integer)
        getDivs_Bad = getDivs
        For Div As Integer = 1 To Number
            If Number Mod Div = 0 Then getDivs.Add(Div)
        Next
    End Function

End Module

Conclusion :


COMMENT CA MARCHE ?
====================

Et bien c'est simple ! (Soit N le nombre)

1) La technique habituelle :
On teste tous les nombres (X) de 0 à N, et si N\X=0, on le prend
Cela veut dire que l'on fait N fois l'opération

2) L'autre technique
On teste tous les nombres jusqu'à ce que le premier diviseurs soit plus grand que le deuxième.

Conctrètement : cherchons les diviseurs de 10 :
1) 1 : Divseur, 2 : Diviseur, 3, 4, 5 : Diviseurs, 6, 7, 8, 9, 10 : Diviseur (10=10 : FIN)
2) 1 et 10 : Diviseurs, 2 et 5 : diviseurs, 3 et 3, (4>2 : FIN)
==> J'ai fais 4 opération, alors qu'il en faut 10 avants :

Concrètement, ce gain s'exprime avec la formule suivante :
1) Opérations = N
2) Opérations = (Racine de N) + 1

Si qqun trouve encore mieux (passer par des arrays déjà triés, ...), qu'il poste, moi j'ai donné le principe, je ne compte pas aprofondir (c'est pas tous les jours qu'on chercher les diviseurs de 852047!)

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
9
Date d'inscription
mercredi 30 janvier 2008
Statut
Membre
Dernière intervention
24 juillet 2008

salut a tout j'ai installer timewatcher mais je ne cé pas comment utilise pour creer des codes merci de me repondre a ce -email kaneassane2008@gmail.com
Messages postés
144
Date d'inscription
lundi 13 octobre 2003
Statut
Membre
Dernière intervention
21 décembre 2014

je l'ai trouvé, j'ai posté il y a quelques semaines les classes BigInt, Complexe (pour les nombres complexes) et matrice (pour le calcul matriciel) qui sont des structures et permettent donc d'utiliser les opérateurs mathématiques usuels et un peu plus... :) tout en VB.NET!
Messages postés
278
Date d'inscription
jeudi 12 janvier 2006
Statut
Membre
Dernière intervention
22 décembre 2008

Oui, d'ailleurs une source a été postée dans ce sens il y a peu... C# peut-être...
Messages postés
144
Date d'inscription
lundi 13 octobre 2003
Statut
Membre
Dernière intervention
21 décembre 2014

bonjour,
c'est pas mal!
est ce qu'il est possible en .NET de définir un nouveau type (BigInt par exemple) et de surcharger les opérations + - / * etc à l'aide d'une classe comme c'est fait en cpp ici? http://www.codeproject.com/useritems/BN.asp ...
Messages postés
278
Date d'inscription
jeudi 12 janvier 2006
Statut
Membre
Dernière intervention
22 décembre 2008

Des fonctions ont été ajoutées ;)
N'hésitez pas à commentez la source ;)
Afficher les 6 commentaires

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.