Optimise the solution to Project Euler 12 (Python)

execute, long-integer, python, time

Solution

My answer here isn't pretty or elegant, it is still brute force. But, it simplifies the problem space a little and terminates successfully in less than 10 seconds.

Getting factors of n: Like @usethedeathstar mentioned, it is possible to test for factors only up to `n/2`. However, we can do better by testing only up to the square root of n:

let n = 36
=> factors(n) : (1x36, 2x18, 3x12, 4x9, 6x6, 9x4, 12x3, 18x2, 36x1)

As you can see, it loops around after 6 (the square root of 36). We also don't need to explicitly return the factors, just find out how many there are... so just count them off with a generator inside of sum():

import math

def get_factors(n):
    return sum(2 for i in range(1, round(math.sqrt(n)+1)) if not n % i)

Testing the triangular numbers

I have used a generator function to yield the 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)
    for i in triangles:
        if get_factors(i) > 499:
            return i

Running this with the profiler, it completes in less than 10 seconds:

$ python3 -m cProfile euler12.py 

361986 function calls in 8.006 seconds

The BIGGEST time saving here is `get_factors(n)` testing only up to the square root of n - this makes it heeeaps quicker and you save heaps of memory overhead by not generating a list of factors.

As I said, it still isn't pretty - I am sure there are more elegant solutions. But, it fits the bill of being faster :)

Problem

I have the following code for Project Euler Problem 12. However, it takes a very long time to execute. Does anyone have any suggestions for speeding it up? ``` n = input("Enter number: ") def genfact(n): t = [] for i 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 the number of triangle numbers to check: ") print for i in xrange (2, m+2): a = sum(xrange(i)) b = len(genfact(a)) if b > 500: print a ``` For n, I enter an arbitrary number such as 6 just to check whether it indeed returns the length of the list of the number of factors. For m, I enter entered 80 000 000 It works relatively quickly for small numbers. If I enter `b > 50` ; it returns 28 for a, which is correct.

Original source