Project Euler #12 runs very slowly

Question

The problem is :

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?

The code works now, when I set the condition in the last loop to 60, etc. instead of 500. But 500 is too big for it and it takes forever to answer (actually I didn't have enough patience to see how much time it takes, it takes a bit too much).

How can I make it faster?

def num_of_divisors(x):
    k=0
    b=x

    while x%2==0:
        x=x//2
        k=k+1
    z=1
    while x!=1:
        for y in range(3,b+1,2):
            a=0
            while x%y==0:
                x=x//y
                a=a+1
            z=z*(a+1)
    return(z*(k+1))

def triangular(n):
    return(n*(n+1)//2)

for n in range(1,10000):
    jk=triangular(n)
    if num_of_divisors(jk)>500:
        print(triangular(n))
        break

Answer 1

You're most of the way there, so I'll give you a hint to avoid spoiling the problem:

• Your function triangular shows that you know that the formula for the \$ n \$th triangular number is $$ T(n) = { n(n+1) \over 2 }. $$ What numbers can possibly be divisors of \$ T(n) \$? Take a look at some small values of \$ n \$ and see if there is a pattern.

As far as code review goes, some quick points:

1. Better choice of variable names would make the code easier to read. For example k and a are essentially the same thing (each is the power of a prime in the factorization of x) so why do they have such different names?

2. y loops over the odd numbers, but if you're solving lots of Project Euler problems then you have probably written a prime number sieve and so you could use that here (and avoid the special case for 2 while you're about it).

3. Use augmented assignment to make the code shorter and simpler, for example, z=z*(a+1) can be written z *= a + 1.

Answer 2

Language

Your tag states Python3. Do note this will also work on Python2.

Style

Your style is not according to Python standards. It would be much better to read if you adhered to the basics of PEP8.

Also, your loop n in range starts at 1 now. What if you want to re-use this code and give invalid input?

Your code would hang if you accidentally started a 0. This would allow triangular(0, resulting in num_of_divisors(0). Such input would cause an infinite loop. It's good practice to prevent hangups (infinite loops) like these. The assert statement is perfect to prevent a script from getting stuck in illegal states.

Performance

The performance is awful. As you stated, 500 is too large for your script. Where 100 takes a couple of seconds, 200 takes over a minute.

According to benchmark(targeting 200, mean in seconds):

           name | rank | runs |  mean |    sd | timesBaseline
----------------|------|------|-------|-------|--------------
num of divisors |    1 |   10 | 85.77 | 1.229 |           1.0

Again, awful. I estimate a run targeting 500 would take over a hundred hours.

The problem is your design isn't optimized, which is because the math behind this is slightly more complicated than you assume. Since Gareth already answered that part, I see no point in repeating this. If learning by example is more your style, take a look at other entries for Euler #12 on Code Review.