i have following code project euler problem 12. however, takes long time execute. have suggestions speeding up?
n = input("enter number: ") def genfact(n): t = [] in xrange(1, n+1): if n%i == 0: t.append(i) return t print "numbers of divisors: ", len(genfact(n)) print m = input("enter number of triangle numbers check: ") print in xrange (2, m+2): = sum(xrange(i)) b = len(genfact(a)) if b > 500: print for n, enter arbitrary number such 6 check whether indeed returns length of list of number of factors. m, enter entered 80 000 000
it works relatively small numbers. if enter b > 50 ; returns 28 a, correct.
my answer here isn't pretty or elegant, still brute force. but, simplifies problem space little , terminates in less 10 seconds.
getting factors of n: @usethedeathstar mentioned, possible test factors n/2. however, can better testing square root of n:
let n = 36 => factors(n) : (1x36, 2x18, 3x12, 4x9, 6x6, 9x4, 12x3, 18x2, 36x1) as can see, loops around after 6 (the square root of 36). don't need explicitly return factors, find out how many there are... count them off generator inside of sum():
import math def get_factors(n): return sum(2 in range(1, round(math.sqrt(n)+1)) if not n % i) testing triangular numbers
i have used generator function yield triangular numbers:
def generate_triangles(limit): l = 1 while l <= limit: yield sum(range(l + 1)) l += 1 and finally, start testing:
def test_triangles(): triangles = generate_triangles(100000) in triangles: if get_factors(i) > 499: return running profiler, completes in less 10 seconds:
$ python3 -m cprofile euler12.py 361986 function calls in 8.006 seconds the biggest time saving here get_factors(n) testing square root of n - makes heeeaps quicker , save heaps of memory overhead not generating list of factors.
as said, still isn't pretty - sure there more elegant solutions. but, fits bill of being faster :)
Comments
Post a Comment