numeri triangolo in pitone

Question

che sto cercando di risolvere il problema:

qual è il valore del primo numero triangolo per avere più di cinquecento divisori?

Un numero triangolo è un numero della sequenza della somma dei numeri cioè 1 + 2 + 3 + 4 + 5 ...

Sono abbastanza sicuro che questo è il codice di lavoro, ma Non lo so perché il mio computer impiega troppo tempo per calcolarlo. Qualcuno ha qualche idea su come rendere il programma un po 'più veloce.
Grazie.

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

Non stai aggiornando il valore di one, in modo che il programma non avrà mai fine.

Answer 2

consigli:

• qual è la formula per n numero triangolare -esimo?
• n e n+1 non hanno fattori comuni (eccetto 1). Domanda: dato numero di fattori in n e n+1 come calcolare il numero di fattori in n*(n+1)? Che dire di n/2 e (n+1) (o n e (n+1)/2)?
• se conoscete tutti i fattori primi di n come calcolare il numero di divisori di n?

Se non si desidera modificare l'algoritmo allora si può rendere più veloce:

• sostituire l.append da factor_count += 1
• enumerare a int(a**.5) invece di a/2 (utilizzare factor_count += 2 in questo caso) .

Answer 3

Dovrai pensare di più e usare meno forza bruta per risolvere le domande del Project Euler.

In questo caso è necessario indagare su quanti e quanti numeri di triangolo hanno i divisori. Inizia dall'inizio, cerca modelli, cerca di capire il problema.

Answer 4

Solo per amor di sanità mentale, è necessario utilizzare

while True: 

e sbarazzarsi di one.

Answer 5

L'algoritmo della forza bruta corrente è troppo inefficiente per risolvere questo problema nel limite di tempo di Project Euler di 1 minuto. Invece, vi suggerisco di guardando la Funzione Sigma:

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

Answer 6

Prima di tutto, le persone che dicono che non si può risolvere questo problema con la forza bruta in meno di un minuto sono sbagliate. Un algoritmo di forza bruta per un problema di queste dimensioni verrà eseguito in pochi secondi.

In secondo luogo, il codice che hai postato ha diversi problemi, alcuni dei quali già menzionati.

• Si dovrebbe terminare il ciclo impostando one ad un valore diverso da 0 una volta a raggiungere il tuo obiettivo condizione (dove è attualmente print a).
• Non si reinizializza mai l'elenco (l = []). Questo dovrebbe essere fatto ogni volta che si ricalcola a e b, proprio prima di inserire il ciclo for.
• La domanda chiede che il primo numero di triangolo abbia su cinquecento divisori. Le condizioni per la risoluzione dovrebbero essere if len(l) > 500:.
• Probabilmente non si desidera print a all'interno del ciclo for, ma attendere fino al termine del ciclo.

La cosa che sta realmente rallentare è che per ogni numero triangolo a si sta controllando ogni valore fino a a/2 per vedere se si tratta di un divisore. È sufficiente verificare i valori fino alla radice quadrata di a. In questo modo per ogni valore di x, se x è un divisore, è sufficiente aggiungere x e a/x all'elenco.

Ecco il codice con le modifiche che ho descritto sopra:

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

Vedrai che venga eseguito in circa 5 o 6 secondi, quindi ben al di sotto di un minuto con queste modifiche.