numéros de triangle en python

Question

Je suis en train de résoudre le problème:

Quelle est la valeur du premier numéro de triangle pour avoir plus de cinq cents? Diviseurs

Un certain nombre de triangle est un nombre dans la séquence de la somme des nombres soit 1 + 2 + 3 + 4 + 5 ...

Je suis assez sûr que ce soit le code de travail mais Je ne sais pas parce que mon ordinateur prend trop de temps à le calculer. Quelqu'un a-t-il une idée de la façon de rendre le programme un peu plus rapide?
Merci.

import math 

def main(): 
    l = [] 
    one = 0 
    a = 1 
    b = 2 
    while one == 0: 
     a = a + b 
     b += 1 
     for x in range(1, int(a/2 + 1)): 
      if a % x == 0: 
       l.append(x) 
       if len(l) > 499: 
        print a 

if __name__ == '__main__': 
    main() 

Answer 1

Vous n'êtes pas mettre à jour la valeur de one, de sorte que votre programme ne prendra jamais fin.

Answer 2

Conseils:

• quelle est la formule pour n -ème nombre triangulaire?
• n et n+1 n'ont pas de facteurs communs (sauf 1). Question: donné le nombre de facteurs dans n et n+1 comment calculer le nombre de facteurs dans n*(n+1)? Qu'en est-il de n/2 et (n+1) (ou n et (n+1)/2)? Comment ajouter le nombre de diviseurs de n?

Si vous ne voulez pas changer votre algorithme, vous pouvez le rendre plus rapide par:

• remplacer l.append par factor_count += 1
• à énumérer int(a**.5) au lieu de a/2 (utiliser factor_count += 2 dans ce cas) .

Answer 3

Vous devrez réfléchir davantage et utiliser moins de force brute pour résoudre les questions de Project Euler.

Dans ce cas, vous devez déterminer le nombre de diviseurs et le nombre de diviseurs. Commencez au début, cherchez des modèles, essayez de comprendre le problème.

Answer 4

Juste pour l'amour de bon sens, vous devez utiliser

while True: 

et de se débarrasser de one.

Answer 5

Votre algorithme de force brute actuel est trop inefficace pour résoudre ce problème dans le délai de Project Euler de 1 minute. Au lieu de cela, je suggère à la recherche à la Diviseur Fonction:

http://www.artofproblemsolving.com/Wiki/index.php/Divisor_function

Answer 6

Tout d'abord, les gens qui vous disent que vous ne pouvez pas résoudre ce problème avec la force brute en moins d'une minute sont erronées. Un algorithme de force brute pour un problème de cette taille s'exécutera en quelques secondes.Deuxièmement, le code que vous avez publié a plusieurs problèmes, certains d'entre eux déjà mentionné.

• Vous devez mettre fin à la boucle en mettant one à une valeur autre que 0 une fois que vous atteignez votre état de but (où vous actuellement print a).
• Vous ne réinitialisez jamais la liste (l = []). Cela devrait être fait chaque fois que vous recalculez a et b, juste avant d'entrer dans la boucle for.
• La question demande que le premier numéro de triangle ait sur cinq cents diviseurs. Votre condition de résiliation doit être if len(l) > 500:.
• Vous ne voulez probablement pas print a à l'intérieur de la boucle for, mais attendez que la boucle while soit terminée.

La chose qui est vraiment vous ralentir est que pour chaque numéro de triangle a vous vérifiez toutes les valeurs jusqu'à a/2 pour voir si elle est un diviseur. Votre seul besoin de vérifier les valeurs jusqu'à la racine carrée de a. De cette façon, pour chaque valeur de x, si x est un diviseur, vous pouvez simplement ajouter x et a/x à la liste.

Voici votre code avec les modifications que je décrit ci-dessus:

import math 

def main(): 
    l = [] 
    one = 0 
    a = 1 
    b = 2 
    while one == 0: 
     a = a + b 
     b += 1 
     l = [] 

     sqrt_a = int(math.sqrt(a)) 

     for x in range(1, sqrt_a + 1): 
      if a % x == 0: 
       l.append(x) 
       if x < math.sqrt(a): 
        l.append(a // x) 
       if len(l) > 500: 
        # print(a) 
        one = 1 

    print(a, b, len(l)) 

if __name__ == '__main__': 
    main() 

Vous verrez qu'il fonctionne dans environ 5 ou 6 secondes, si bien moins d'une minute avec ces modifications.