Krdytkyu

I'm a beginner to programming and just started python, I've been trying to work through Project Euler challenges.

I wrote a program to solve Project Euler #12, which asks for the smallest number of the form 1+ 2 + 3 + … + n which has over 500 divisors. It works perfectly with smaller numbers like 100, but takes too long trying to find up to 500 factors. I gave up waiting after about 20 minutes. I'd like some help with optimizing my code to make it faster.

I basically made a function that finds the triangular number of a given number and another function that counts the number of factors/divisors of a number. I made a while loop where a number keeps increasing till the triangular number of itself has more than 500 factors.

And here is my code:

#Starts the timer to measure time taken for code to run:

import time

start_time = time.time()



#Returns the triangular number of 'num':

def triangular(num):

    return int((num*(num+1))/2)



#Returns the number of factors(divisors) of 'num':

def facCount(num):

    summ = 0

    for i in range(1, num+1):

        if num % i == 0:

            summ += 1

    return summ



#Declares x (starting value):

x = 0



#main:



while True:

    #Checks if number of factors for the triangular of x is above 500

    if facCount(triangular(x)) > 500:

        #Sets the value of 'ans' to the triangular of 'x':

        ans = triangular(x)

        #Exits the loop since answer is found

        break

    x += 1



#Prints answer (the first triangular number that has more than 500 factors):

print(ans)



#Prints the time taken for code to execute:

print("--- %s seconds ---" % (time.time() - start_time))

Your function facCount, which should be called something like count_factors, according to Python's official style-guide, PEP8, can be greatly improved by noticing that if num % i == 0, then automatically num % num / i == 0 (in other words, factors always come in pairs of two, except for if the number is a square, in which case you double count one). This means you only need to check factors up to $sqrt{n}$:

from math import sqrt



def count_factors(num):

    """Return the number of factors of `num`"""

    sum_ = 2 * sum(num % i == 0 for i in range(1, int(sqrt(num)) + 1))

    if int(sqrt(num))**2 == num:

        sum_ -= 1

    return sum_

I also added a docstring describing what the function does in an accessible way.

The other improvement concerns the way you get the triangular numbers. While it is good to know Gauss formula, IMO it is here easier to manually calculate them. Your function needs to do one increment, one multiplication and one division, when all you really need is one addition per loop iteration:

from itertools import count



def triangular_nums():

    """Yield the triangular numbers"""

    t = 0

    for i in count():

        t += i

        yield t

If, for some reason, you dislike itertools, you can also replace it with a while True loop.

In Python 3+, you can use the new function itertools.accumulate (3.2+) and the new keyword combination yield from (3.3+), as mentioned in the comments by @MaartenFabré:

from itertools import accumulate, count



def triangular_nums():

    yield from accumulate(count())

With this your main function (which you should either make a real function or at least put under an if __name__ == "__main__": guard) becomes:

def main():

    for t in triangular_nums():

        if count_factors(t) > 500:

            return t



if __name__ == "__main__":

    ans = main()

    if ans is not None:

        print(ans)

The timing you should factor out and make into a decorator:

import time



def timeit(func):

    def wrapper(*args, **kwargs):

        start = time.time()

        ret = func(*args, **kwargs)

        print("--- %s seconds ---" % (time.time() - start))

        return ret

    return wrapper



@timeit

def main():

    ...

The point of this particular Project Euler question is to teach you about the number-of-divisors function.

def triangular(num):

    return int((num*(num+1))/2)



#Returns the number of factors(divisors) of 'num':

def facCount(num):

    summ = 0

    for i in range(1, num+1):

        if num % i == 0:

            summ += 1

    return summ

Observe that some of the factors of triangular(n) are also factors of triangular(n+1). Why? How can you use that reason to avoid doing the same work more than once?

Leaving aside the algorithmic considerations,

def triangular(num):

    return int((num*(num+1))/2)

doesn't need int if you use integer division:

def triangular(num):

    return num * (num + 1) // 2

You have to check against until num/2, num/2 is the largest factor for a even number, the sqrt is to get the largest prime factor. And attach itself to the list at last.