Discussion :

[mayeux67]

Bonjour,

J'essaye tant bien que mal de résoudre le problème d'Euler n°12 (https://projecteuler.net/problem=12)

Mon problème, c'est que ma macro est trop gourmande en calcul et du coup, vraiment longue à s'exécuter.
A chaque lancement de la macro, Excel tombe en mode "ne répond pas" et j'ai pas eu la patience d'attendre plus de 4min après le lancement de la macro. Avec un Ctrl+Pause aux environs de 4min, j'en suis au nombre triangulaire 7 279 020 qui admettrais (au moins) 142 diviseurs.

Mon programme semble fonctionner pour de petits nombres, donc ma question n'est pas de trouver une réponse au problème n°12, mais plutôt de m'aider à réduire le temps d'exécution de ma macro.


mon code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
Sub prob12()
 
Dim a As Long
Dim nb_diviseur As Long
Dim diviseur As Long
Dim nb_triangle As Long
 
a = 3
nb_triangle = 3
 
For a = 3 To 20000000
 
    diviseur = 1
    nb_diviseur = 0
    Do While nb_diviseur < 500
 
        If nb_triangle Mod diviseur = 0 Then
            diviseur = diviseur + 1
            nb_diviseur = nb_diviseur + 1
        Else
            If diviseur > nb_triangle / 2 Then
                nb_diviseur = nb_diviseur + 1
                Exit Do
            Else
                diviseur = diviseur + 1
            End If
        End If
 
    Loop
    If nb_diviseur >= 500 Then
        MsgBox nb_triangle & " est le premier nombre triangulaire admettant plus de 500 diviseurs"
        End
    End If
    nb_triangle = nb_triangle + a
Next
 
 
End Sub

Merci d'avance pour vos conseils

Mayeux67

[eriiic]

Bonjour,

vu que tu travailles avec des entiers ça va être assez difficile d'accélérer en gardant le même algorithme je pense.
Une proposition : tu pourrais essayer en décomposant en facteurs premiers et en construisant une table de nombres premiers au fur et à mesure.
eric

[clementmarcotte]

Bonjour,

Tu ne dois pas oublier que VBA est un langage interprété et non un langage compilé. Puisque chaque instruction est interprétée chaque fois qu'elle doit être exécutée (une boucle de 10 instructions exécutée 10 fois donne 100 conversions en langage-machine) la meilleure façon d'optimiser un programme est probablement de réduire le nombre d'instructions, en utilisant le meilleur algorithme disponible.

[mayeux67]

Bonjour,

Merci pour vos réponses,

@eriiic : une décomposition en facteurs premiers me donnerait, pour un nombre donné, une liste de nombres premiers. Il faudrait alors que je compose avec cette liste pour trouver tous les diviseurs du nombre donné .. On gagnera certes du temps en faisant la décomposition en facteurs premiers mais la recherche de tous les diviseurs à partir de cette décomposition me parait un peu compliqué non ?

D'autant plus qu'avec mon niveau actuel de VBA, je ne sais pas utiliser de tableau, et encore moins un tableau dynamique ..

Je vais néanmoins travailler sur cette idée, mais il me faudra de l'aider pour créer la code qui gère le tableau (entre autre)

@clementmarcotte : j'avais bien saisi qu'une boucle dans un boucle ça fait faire plus de travail à la machine C'est pour ça que je suis venu ici pour avoir des conseils, parce que d'un coté, mes connaissances en VBA me permettent pas pour le moment d'améliorer cet algorithme, et de l'autre coté, mes connaissances en maths sont un peu rouillées pour élaborer un autre algorithme.

Est-ce que par exemple séparer les boucles permettrait de réduire le temps d'éxecution ? dans un premier temps chercher les nombres triangulaires et les stocker dans un tableau et après faireun boucle à part pour tester ces nombres triangulaires et leurs nombres de diviseurs. Si on trouve aucun résultat qui à plus de 500 diviseurs, on augmente le nombre de nombre triangulaire à chercher dans la 1° boucle ?


++
Mayeux67

[eriiic]

Bonjour,

Est-ce que par exemple séparer les boucles permettrait de réduire le temps d'éxecution ? dans un premier temps chercher les nombres triangulaires et les stocker dans un tableau et après faireun boucle à part pour tester ces nombres triangulaires et leurs nombres de diviseurs.

Peut-être, tout dépend si tu ne perds pas plus de temps dans la recherche des diviseurs. Là aussi te générer une table des nombres premiers te fera gagner un temps considérable.

Pour générer tes nombres triangulaires utilises somme des n premiers entiers = n(n+1)/2 plutôt que de balayer tous les nombres.

eric

[mayeux67]

Re,

Je n'avais pas pensé à utiliser n(n+1)/2, merci pour le tuyaux

Concernant le tableau des nombres premiers, j'ai déjà une macro qui me donne le Xieme nombre premier que je peux modifier pour les besoins de ce problème.
Pour le tableau, voici un bout de code pour l'utilisation du dit tableau :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
Dim tblnbprem() As Integer
Dim i As Integer
ReDim tblnbprem(i + 1)
tblnbprem(i) = nbre 'nbre est le nombre premier de rang i

le redim et l'affectation seront placé dans une boucle qui me calcul le nombre premier n°i.
Est-ce que je peux déjà partir sur un tableau de ce type ? niveau syntaxe il est bien définit ?

Merci d'avance,
Mayeux67

[eriiic]

oui, mais as Long pour les 2 plutôt.
eric

[mayeux67]

Re,

ok merci, je vais changer cela.

Par contre, j'ai modifié le petit bout de code du tableau pour que dans une boucle les valeurs soient conservées

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

ReDim Preserve tblnbprem(i + 1)

Maintenant que j'ai ma liste de nombres premiers dans un tableau, je vais m'attaquer à la décomposition en facteurs premiers.

Merci pour l'aide.
J'aurais certainement d'autres questions par la suite, je les posterais ici

Mayeux67

[eriiic]

Au passage tu as = n(n+1)\2 (\ au lieu de /) qui est la division entière. Sans doute un peu de temps de gagné encore.
eric

[mercatog]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
Sub Euler12()
Const CST As Integer = 500
Dim Y As Long, i As Long, Tm As Long
Dim N As Integer
 
Tm = Timer
Do
    DoEvents
    i = i + 1
    Y = Y + i
    N = NbDiv(Y)
Loop Until N >= CST
 
MsgBox "Nombre de diviseurs: " & N & vbNewLine & "Nombre trouvé: " & Y & vbNewLine & "En " & Timer - Tm & " secondes"
End Sub
 
Private Function NbDiv(ByVal N As Long) As Integer
Dim i As Long, P As Long
Dim S As Integer
 
i = 2
P = N
Do While i < P
    P = N / i
    S = S - (1 - (P <> i)) * (N Mod i = 0)
    i = i + 1
Loop
NbDiv = S + 1
End Function

[mayeux67]

Re,

@eric : vu que n(n+1) est toujours pair, la division entière est elle utile ?

@mercatog ; c'est bien gentil de donner la solution mais ce n'est pas vraiment ce que je cherche .. en plus sans un minimum de commentaire, t'es i, S, P, N, etc .. sont un peu indigeste (pour moi en tout cas) merci quand même



Mayeux67

[eriiic]

Bonjour,

@eric : vu que n(n+1) est toujours pair, la division entière est elle utile ?

C'est surtout parce que tu veux un résultat entier que tu peux l'utiliser.
Vu que ce n'est pas le même algorithme et qu'elle est 30% plus rapide c'est toujours du temps de gagné facilement. Même si c'est pas là dessus que tu gagneras beaucoup.

eric