Simple code that finds number of factors crashes my computer. Is there a workaround for a large number? This is my attempt at problem 12 from Project Euler. However, my code freezes my old, linux computer when I run it. I've only got 512MB of RAM and an old Intel Core 2 Duo processor on my machine which, I assume, is why it can't run the code.

Is there a way to optimize this code without using up too much resources?

#!/bin/python

def nth_triangle_number(nth):
    """ 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. """
    return sum([i for i in range(nth+1)]) 

def get_number_of_factors(num):                 
    quantity = 0
    for i in range(1, int(num/2)+1):     # I think the problem lies here in range()
        if not num % i:                  # BTW, using math.sqrt() produces the wrong
            quantity += 1                # answer for smaller numbers. I don't know why.
    return quantity + 1     # Added 1 to count for num (as in 1 * num)

def get_triangle_number(divisors):
    """ Find the triangle number with the given amount of divisors """
    i = 1
    while get_number_of_factors(nth_triangle_number(i)) &lt;= divisors:
        i += 1

    return nth_triangle_number(i)

if __name__ == '__main__':
    number_of_divisors = 500
    print "Answer found: ", get_triangle_number(number_of_divisors)


I've tried initializing get_triangle_number(), i, at higher values, but it didn't seem to help. I believe the problem is with get_number_of_factors(). I had originally stored all the factors of a given integer into a list then compared its length to number_of_divisors. I figured counting each integer that satisfied the condition would save some resources.

The code does run properly and produces the correct answer when I tested the example provided on Project Euler and the following values:

    number_of_divisors = 5      # Runs properly and produces correct answer
    number_of_divisors = 50     # Runs properly and         "    "
    number_of_divisors = 150    # Runs properly and         "    "
    number_of_divisors = 200    # Crash
First, you can easily find the bottleneck in your code by running it with the profiler (ran with number_of_divisors = 100):

~&gt; python -m cProfile t.py
Answer found:  73920
         1926 function calls in 0.522 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.522    0.522 t.py:1(&lt;module&gt;)
      385    0.006    0.000    0.008    0.000 t.py:1(nth_triangle_number)
        1    0.000    0.000    0.522    0.522 t.py:13(get_triangle_number)
      384    0.472    0.001    0.514    0.001 t.py:6(get_number_of_factors)
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
      769    0.043    0.000    0.043    0.000 {range}
      385    0.001    0.000    0.001    0.000 {sum}


You can immediately see that:


Indeed, get_number_of_factors() slows everything down;
You can slightly optimize things by replacing range with xrange (which does not create a list).


In your case get_number_of_factors() is a good example of a function that requires algorithmic optimization. Currently it has O(N) complexity. As you correctly guessed, iterating only till sqrt(num) will make it faster:

def get_number_of_factors(num):

    limit = math.sqrt(num)
    int_sqrt = int(round(limit))

    if int_sqrt ** 2 == num:
        int_limit = int_sqrt
        quantity = 1
    else:
        int_limit = int(limit) + 1
        quantity = 0

    for i in xrange(1, int_limit):
        if not num % i:
            quantity += 2

    return quantity


Some highlights:


math.sqrt returns a float, so if you want to be extra-safe, you need to convert it to integer properly (if sqrt(4) gives you 3.9999999, just int() will produce 3).
When you are iterating to the square root, each factor you found stands for two factors: i and num / i.
But you do not want to include the root itself, because if num is a perfect root, you only need to count sqrt(num) once.


This makes your algorithm run in O(sqrt(N)). 
Edit: if you want even more performance, you can try to implement number field sieve.

To add more performance, you can replace the direct sum in nth_triangle_number() with a known formula for arithmetic progression.
The result is:

import math

def nth_triangle_number(nth):
    """ 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.
        Using the fact that 1 + ... + n = n * (n + 1) / 2
        """
    return nth * (nth + 1) / 2

def get_number_of_factors(num):

    limit = math.sqrt(num)
    int_sqrt = int(round(limit))

    if int_sqrt ** 2 == num:
        int_limit = int_sqrt
        quantity = 1
    else:
        int_limit = int(limit) + 1
        quantity = 0

    for i in xrange(1, int_limit):
        if not num % i:
            quantity += 2

    return quantity

def get_triangle_number(divisors):
    """ Find the triangle number with the given amount of divisors """
    i = 1
    while get_number_of_factors(nth_triangle_number(i)) &lt;= divisors:
        i += 1

    return nth_triangle_number(i)

if __name__ == '__main__':
    number_of_divisors = 100
    print "Answer found: ", get_triangle_number(number_of_divisors)


And it runs much faster now. For 100:

~&gt; python -m cProfile t.py 
Answer found:  73920
         1540 function calls in 0.007 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.007    0.007 t.py:1(&lt;module&gt;)
      384    0.006    0.000    0.006    0.000 t.py:10(get_number_of_factors)
        1    0.000    0.000    0.006    0.006 t.py:28(get_triangle_number)
      385    0.000    0.000    0.000    0.000 t.py:3(nth_triangle_number)
      384    0.000    0.000    0.000    0.000 {math.sqrt}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
      384    0.000    0.000    0.000    0.000 {round}


And for 500:

~&gt; python -m cProfile t.py 
Answer found:  76576500
         49504 function calls in 5.364 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    5.364    5.364 t.py:1(&lt;module&gt;)
    12375    5.342    0.000    5.349    0.000 t.py:10(get_number_of_factors)
        1    0.010    0.010    5.363    5.363 t.py:28(get_triangle_number)
    12376    0.005    0.000    0.005    0.000 t.py:3(nth_triangle_number)
    12375    0.003    0.000    0.003    0.000 {math.sqrt}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
    12375    0.004    0.000    0.004    0.000 {round}