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!)
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.