1
\$\begingroup\$

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))
\$\endgroup\$
1
  • 1
    \$\begingroup\$ (Welcome to CR!) With every self-respecting programming challenge, brute force is going to be too slow no matter how competently coded: think (and tag) algorithm. \$\endgroup\$ Commented Mar 30, 2018 at 10:38

3 Answers 3

Reset to default
4
\$\begingroup\$

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():
    ...
\$\endgroup\$
7
  • \$\begingroup\$ Actually, sorry for the late reply, but could you expand the count_factors function by using a multi-line for loop instead of the single line ones you used, I'm kinda unfamiliar with single-line for loops. Thanks. \$\endgroup\$ Commented Apr 18, 2018 at 12:59
  • \$\begingroup\$ @Flaming_Dorito In that case you should make yourself familiar with Python's list-comprehensions/generator-expressions. This particular one is roughly equivalent to: gist.github.com/graipher/cbdf5bbcaa7e30f48392e04f85fec9e6 \$\endgroup\$ Commented Apr 18, 2018 at 13:03
  • \$\begingroup\$ Thanks, good idea, I probably should :) Also, I managed to make it a multiline function: pastebin.com/xV6yU7Ai But it was faster than the one you provided, I'm kinda confused since it does the exact same thing as your function. I figured it should take the same time. But it takes approximately a fifth of the time almost every time. \$\endgroup\$ Commented Apr 18, 2018 at 13:20
  • \$\begingroup\$ You can see the time difference by running this: pastebin.com/fuRPfg4H \$\endgroup\$ Commented Apr 18, 2018 at 13:24
  • \$\begingroup\$ @Flaming_Dorito I also see a difference (but less than a factor 2. Try using sum(1 for i in range(1, int(sqrt(num)) + 1) if num % i == 0) in count_factors, then it is faster than the naive for loop. The difference is that the intermediate list that is produced gets smaller. \$\endgroup\$ Commented Apr 18, 2018 at 14:20
2
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ are you assuming num will always be an even number? \$\endgroup\$ Commented Dec 16, 2018 at 6:36
  • \$\begingroup\$ Actually, you can count factors whilst iterating only to √num, since factors come in pairs. Do remember the special case where num is a perfect square, though, and count √num only once then. \$\endgroup\$ Commented Jan 10, 2019 at 18:26

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.