números de triángulo en pitón

Question

que estoy tratando de resolver el problema:

Cuál es el valor del primer número de triángulo para tener más de quinientos divisores?

Un número triángulo es un número en la secuencia de la suma de los números, es decir, 1 + 2 + 3 + 4 + 5 ...

Estoy bastante seguro de que este es el código de trabajo, pero No lo sé porque mi computadora tarda demasiado en calcularla. ¿Alguien tiene alguna idea de cómo hacer que el programa sea un poco más rápido?
Gracias.

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

No está actualizando el valor de one, por lo que su programa no tendrá fin.

Answer 2

Consejos:

• ¿cuál es la fórmula para n -ésimo número triangular?
• n y n+1 no tienen factores en común (excepto 1). Pregunta: dado el número de factores en n y n+1 cómo calcular el número de factores en n*(n+1)? ¿Qué pasa con n/2 y (n+1) (o n y (n+1)/2)?
• si conoce todos los factores primos de n como calcular el número de divisiones de n?

Si no desea cambiar su algoritmo, entonces puede hacerlo más rápido por:

• reemplazar l.append por factor_count += 1
• enumerar a int(a**.5) en lugar de a/2 (factor_count += 2 utilizar en este caso) .

Answer 3

Tendrás que pensar más y usar menos fuerza bruta para resolver las preguntas de Project Euler.

En este caso, debe investigar cuál y cuántos divisores tienen los números del triángulo. Comience por el principio, busque patrones, intente comprender el problema.

Answer 4

Sólo por el bien de la cordura, se debe utilizar

while True: 

y deshacerse de one.

Answer 5

Su algoritmo actual de fuerza bruta es demasiado ineficiente para resolver este problema en el límite de tiempo de Project Euler de 1 minuto. En lugar de ello, sugiero buscando en la función divisor:

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

Answer 6

En primer lugar, la gente que le dice que no se puede resolver este problema con la fuerza bruta en menos de un minuto están equivocados. Un algoritmo de fuerza bruta para un problema de este tamaño se ejecutará en unos pocos segundos.

En segundo lugar, el código que ha publicado tiene varios problemas, algunos de ellos ya mencionados.

• Debe terminar el bucle mediante el establecimiento de one a un valor distinto a 0 vez que alcance su condición de objetivo (donde se encuentra actualmente print a).
• Nunca reinicializar la lista (l = []). Esto debe hacerse cada vez que recalcula a y b, justo antes de ingresar al ciclo for.
• La pregunta pide que el primer número de triángulo tenga sobre quinientos divisores. Su condición para la terminación debe ser if len(l) > 500:.
• Probablemente no desee print a dentro del bucle for, pero espere hasta que termine el bucle while.

Lo que realmente afectar el rendimiento es que para cada número de triángulo a se esté examinando cada valor de hasta a/2 para ver si es un divisor. Solo debe verificar los valores hasta la raíz cuadrada de a. De esta forma para cada valor de x, si x es un divisor, puede agregar x y a/x a la lista.

Aquí es el código con las modificaciones que he descrito:

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() 

Verás que se ejecuta en unos 5 o 6 segundos, tan bien menos de un minuto con estas modificaciones.