Optimiser macro : problème d'Euler n°12

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:

---

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

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

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.

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

Bonjour,

Citation:

---

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

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:

---

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

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

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:

---

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

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

Code:

---

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

---

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

Bonjour,

Citation:

---

@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