Project Euler Problem #12 - Highly divisible triangular number

Question

Project Euler Problem #12

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

I know this question has been asked here many times regarding long run times (my problem) but I don't understand the explanations so here is my take;

def euler_12(num):
    i = 0
    for n in range(1,num):
        list= []
        for j in range(1, n**2):
            if (n+i) % j == 0:
                list.append(j)
                if len(list) == 500:
                    print(n+i)
                    break
        i = i + n

euler_12(num)

I understand this is probably a very poor way to do it, and it also takes forever to run, so any comments are highly appreciated.

Answer 1

Split up your code. You're:

1. Generating all triangle numbers.
2. Factorizing all triangle numbers.
3. Displaying when you get the first triangle number with 500 or more factors. And ending the program.

These sound like some good functions to me.

And so you could use:

def triangle_numbers():
    return ...

def factors(number):
    return ...

def euler_12():
    for number in triangle_numbers():
        if len(factors(number)) >= 500:
            return number

print(euler_12())

---

To generate all triangle numbers you can use itertools.count and itertools.accumulate. If you're not running Python 3 you can implement accumulate, or manually perform the calculations yourself.

import itertools

# Python 3
def triangle_numbers():
    return itertools.accumulate(itertools.count())

# Python 2
def triangle_numbers():
    sum = 0
    for i in itertools.count():
        sum += i
        yield sum

---

Currently your factors code would be:

def factors(num):
    list= []
    for j in range(1, num**2):
        if (num) % j == 0:
            list.append(j)

This has a couple of problems.

1. You don't need to use num ** 2. The largest maximum you need is num + 1.

2. You can use int(num ** 0.5) + 1.

   This is as \$\sqrt{n}^2 = n\$. With the equation \$n = a * b\$, allowing you to find \$a\$ when you've found \$b\$.

And so you can use:

def factors(num):
    for div in range(1, int(num**0.5) + 1):
        if num % div == 0:
            yield div
            other = num // div
            if other != div:
                yield other

This has change this piece of code from \$O(n^2)\$ to \$O(\sqrt{n})\$. So if \$n = 10000\$, you'd only need to check \$100\$ numbers, rather than \$100000000\$.

You will also have to change the return value of factors to a list to use len.