J'ai essayé de résoudre un problème pour trouver le premier nombre triangulaire avec plus de 500 diviseurs mais il y a une erreur de débordement

S'il vous plaît, donnez un meilleur moyen

La question est

La séquence des nombres triangulaires est générée en ajoutant les nombres naturels. Ainsi, le 7ème numéro de triangle serait 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. Les dix premiers termes seraient:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66 ...

Énumérons les facteurs des sept premiers nombres triangulaires: 1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1 , 3,7,21 28: 1,2,4,7,14,28 Nous pouvons voir que 28 est le premier nombre triangulaire à avoir plus de cinq diviseurs. Quelle est la valeur du premier nombre de triangle à avoir plus de cinq cents diviseurs?

Mon programme est

`
def isPrime(a):
    m=0
    for j in range(1,a/2+1):
        if (a%j)==0:
            m+=1
    return m+1
i=1
n=1
div=500
while (i>=1):
    l=isPrime(i)
    ans=i
    if l>div:
        print ans
        break
    n+=1
    i=n*(n+1)/2
`
1
jainaman224 10 juil. 2015 à 19:17

2 réponses

Meilleure réponse

La clé de ce problème est de savoir comment rendre votre programme plus efficace, vous devez écrire quelque chose qui calcule le nombre de diviseurs d'un entier de manière plus efficace. Il y a beaucoup de discussions sur la façon de faire cela dans ce forum, comme ici: Quel est le meilleur moyen d'obtenir tous les diviseurs d'un nombre? Cependant, je pense toujours que votre programme a quelques problèmes, alors j'en ai écrit un (toujours en utilisant votre méthode de recherche du nombre de diviseurs):

def numberOfDivisors(a):
    m=0
    for j in range(1,a/2+1):
        if (a%j)==0:
            m+=1
    return m+1

def findNumber():
    n = 1
    i = 1
    div = numberOfDivisors(n)
    while div < 500:
        i += 1        
        n = i*(i+1)/2
        div = numberOfDivisors(n)
        print 'n = ', n
    return n

L'impression inutile est là juste pour faciliter le suivi du fonctionnement du code. Comme je l'ai dit, toujours en utilisant la très mauvaise méthode de recherche du nombre de diviseurs. Le rendre efficace est le moyen de résoudre la question. Ce programme ne fonctionnera pas comme vous le souhaitez, car il sera trop lent lorsqu'il atteindra des nombres à 6 ou 7 chiffres.

1
Community 23 mai 2017 à 11:48

Un moyen simple mais plus efficace de trouver le nombre de diviseurs consiste à utiliser la factorisation première du nombre pour générer le nombre de diviseurs. La recherche de la factorisation principale est bien documentée, mais je suggérerais d'utiliser un "Tamis d'Ératosthène" ou quelque chose du genre (lien vers le wiki)

Une fois que vous avez la factorisation premier, il vous suffit de trouver le nombre de permutations qui existent de 0 à la puissance de chaque premier dans la factorisation comme décrit ici. Pas besoin de trouver tous les facteurs :)

C'est ainsi que je viens de trouver la solution à ce même problème, et mon programme a pu tester les 12 375 premiers nombres triangulaires en un peu moins de 9 secondes.

Edit: Je dois mentionner que vous devez probablement vous pencher sur les fonctions récursives si vous souhaitez poursuivre cette méthode, car vous en aurez besoin pour trouver toutes les permutations des puissances trouvées dans la factorisation principale

0
mscottchristensen 27 oct. 2016 à 19:22