Lucas Willems

LUCAS WILLEMS

Un étudiant de 21 ans passionné par les maths et la programmation

English

Project Euler 12 : solution Python

Article

Voici un résumé de l'énoncé du problème 12 "Highly divisible triangular number" du Project Euler (traduction complète en français ici) :

What is the value of the first triangle number to have over five hundred divisors?

Compréhension du problème

Reformulons le problème : il nous faut trouver le plus petit nombre triangulaire possédant 500 diviseurs. Comme pour le problème 10 sur la somme des nombres premiers, nous pouvons résoudre ce problème en regardant pour chaque nombre triangulaire le nombre de diviseurs qu'il possède.

Le programme

Voici le programme Python que l'on peut utiliser pour résoudre le problème :

def divisors(nb, extremum = False):
    divisors = []
    inf = 1 if extremum else 2
    for i in range(inf, int(nb**0.5)+1):
        q, r = divmod(nb, i)
        if r == 0:
            if q >= i:
                divisors.append(i)
                if q > i:
                    divisors.append(nb//i)
    return divisors
#Initialisation du premier nombre triangulaire à 3
triangle = 3
i = 2
nb_divisors = 0
while nb_divisors < 500:
    #Calcul du nouveau nombre triangulaire
    i += 1
    triangle += i
    #Récupération du nombre de diviseurs qu'il possède
    nb_divisors = len(divisors(triangle, True))
print(triangle)

Notez que ce programme met plus de temps (≈ 30 secondes) que ceux précédents pour résoudre ce problème car il doit récupérer les diviseurs d'un nombre conséquent de nombres. Il est alors possible de trouver, je pense, une solution plus rapidement et plus optimale pour ce problème. Ce programme ne demande pas d'explications particulières. Toutefois, la fonction divisors est explicitée dans cet article.

Le résultat

La réponse à ce problème est 76576500.

Recherche

Voici les recherches relatives à cette page :

Commentaires

Qu'en pensez-vous ? Donnez moi votre avis (positif ou négatif) pour que je puisse l'améliorer.