Wie verbessert man diese Lösung?

Question

Divisoren von 42 sind: 1, 2, 3, 6, 7, 14, 21, 42. Diese quadrierten Teiler sind: 1, 4, 9, 36, 49, 196, 441, 1764. Die Summe der quadrierten Teiler ist 2500, das ist 50 * 50, ein Quadrat!

Gegeben zwei Integer m, n (1 < = m < = n) wir wollen alle ganzen Zahlen zwischen m und n finden, deren Summe der quadrierten Teiler selbst ein Quadrat ist. 42 ist eine solche Nummer.

Das Ergebnis wird ein Array von Arrays sein, jedes Subarray hat zwei Elemente, zuerst die Zahl, deren quadratische Teiler ein Quadrat ist und dann die Summe der quadrierten Divisoren.

Beispiele:

list_squared (1, 250) -> [[1, 1], [42, 2500], [246, 84100]]

list_squared (42, 250), - > [[42, 2500], [246, 84100]]

oben ist der Ausbilder der Frage.

Ich habe ein Problem, wenn die Praxis von Coderwars. mein Code hat alle Tests bestanden, aber habe einen Fehler "Timeout", es bedeutet, dass mein Code nicht sehr gut ist.wie kann ich es verbessern. Unten ist meine Lösung.

from math import sqrt 
def get_div(x): 
    s = [] 
    for i in range(1,x): 
     if x%i == 0: 
      # print i, x/i 
      s.append(i) 
      s.append(x/i) 
    return set(s) 

def list_squared(m, n): 
    p = [] 
    for i in range(m,n): 
     if i == 1: 
      p.append([1,1]) 
      continue 
     s = sum(a**2 for a in get_div(i)) 
     if float(sqrt(s)).is_integer(): 
      p.append([i,s]) 
    return p 

Answer 1

Basierend auf der Antwort auf diese Frage Algorithm to calculate the number of divisors of a given number und dem Kommentar von @ devin-white möchten Sie vielleicht die folgende Lösung versuchen.

def divisors_squared_sum(x): 
    limit = x 
    squared_sum = 0 
    if x==1: 
     return 1 
    i = 1 
    while True: 
     if x % i == 0: 
      limit = x/i 
      if limit != i: 
       squared_sum += limit**2 
      squared_sum += i**2 
     i += 1 
     if i >= limit: 
      return squared_sum 

def list_squared2(start, end): 
    res = [] 
    for i in xrange(start, end): 
     squared_sum = divisors_squared_sum(i) 
     sqrt_sum = np.sqrt(squared_sum) 
     if int(sqrt_sum) == sqrt_sum: 
      res.append([i, squared_sum]) 

    return res 

ich folgende Ergebnisse:

In [24]: %timeit list_squared(1, 250) 
100 loops, best of 3: 3.6 ms per loop 

In [25]: %timeit list_squared2(1, 250) 
100 loops, best of 3: 1.96 ms per loop 

Answer 2

Zwei Dinge, die ich würde vorschlagen:

1) Statt get_div und Rückgabe eines Arrays, warum es nicht ändern get_div_squared_sum und nur die Summe zurückgeben? Sie verwenden das Array nur zur Summe, wenn Sie also nur die Summe in der Funktion berechnen, verlieren Sie eine ganze for-Schleife.

2) Es wurde bereits erwähnt, aber Sie müssen nur nach sqrt (x) gehen, um alle möglichen Teiler zu erhalten.