How to make my program more efficient in Python

Question

So I had to make a code which generates the first triangle number which has over 500 factors. The problem is given in detail below:

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 have written a block of code which generates the same however it is highly inefficient; kindly suggest some ways to improve it. Moreover it is so inefficient that it only works with numbers below 70

My code is given below, please refer:

def generates_triangle_numbers_upto_n(n):
    list = [1]
    while len(list)<n:
        nth = int(len(list)+1)
        to_be_appended = nth/2 + nth**2/2
        list.append(to_be_appended)
    return list

def return_number_of_n(n):
    num = 0
    for i in range(2, int(n)):
        if n%i == 0:
            num = num+1
    return num + 2

def main(n):
    list = generates_triangle_numbers_upto_n(20000)
    for i in list:
        if return_number_of_n(i) >  int(n):
            return i

print(main(100))

I saw a similar question on this site but I didn't understand how it worked:

Thanks a lot!

Edit 1: Thanks everyone for the wonderful suggestions, based on which I have refined my code:

def main(n):
    list = [1]
    while return_number_of_n_second(list[len(list)-1]) <= n:
        nth = int(len(list)+1)
        to_be_appended = int(nth/2 + nth**2/2)
        list.append(to_be_appended)
    return list[len(list)-1]

def return_number_of_n_second(n):
    num = 0
    import math
    sqrt = math.sqrt(n) 
    for i in range(2, math.ceil(math.sqrt(n))):
    if n%i == 0:
        num = num+1
    if int(sqrt) == sqrt:
        return num*2 +3
    return num*2 + 2

print(main(500))

However, now too, it takes 10-15 seconds to execute. Is there a way to make it even more efficient since almost all of project euler's problems are to be executed in 2-3 seconds max?

You might want to take a look at https://stackoverflow.com/questions/37176767/how-to-find-the-amount-of-factors-that-triangle-numbers-have — niemmi, May 17 '16 at 03:25
Possible duplicate of [Algorithm to calculate the number of divisors of a given number](http://stackoverflow.com/questions/110344/algorithm-to-calculate-the-number-of-divisors-of-a-given-number) — Paul Hankin, May 17 '16 at 03:30
It's not literally a dupe of course, but if you make the part of your code that counts divisors efficient, then your code should be fast enough. — Paul Hankin, May 17 '16 at 03:32
Hint: `tri(n)=n(n+1)/2`, and `n` and `n+1` have no common factors, and one of them must be even. Note that Project Euler do not like it when people publish solutions to PE problems, and PE fans on SO may downvote PE questions and answers. — PM 2Ring, May 17 '16 at 03:41
on a cursory glance you are constantly appending a list ,you might achieve better results using a deque . — Bg1850, May 17 '16 at 03:48
By the way, your code has a bug -- it should test for "at least 500 factors", not "exactly 500 factors" — Paul Hankin, May 17 '16 at 04:00
Check my [answer](https://stackoverflow.com/questions/37176767/how-to-find-the-amount-of-factors-that-triangle-numbers-have/37177367#37177367) in the question I linked to. It runs in 0.3 sec on my machine — niemmi, May 17 '16 at 05:08
If your code is working, isn't [codereview.se] the better place to ask? — Jongware, May 17 '16 at 06:34

score 0 · Answer 1 · answered May 17 '16 at 05:47

0

Just some basic technical optimizations and it should do it:

import time
import math


def main(n):
    last, length = 1, 1

    while return_number_of_n_second(last) <= n:
        length += 1
        last = int(length/2 * (length+1))

    return last


def return_number_of_n_second(n):
    sqrt = math.sqrt(n)
    if int(sqrt) == sqrt:
        return 2
    return sum(1 for i in range(2, math.ceil(sqrt)) if not n % i) * 2 + 2

start_time = time.time()
print(main(500))
print(time.time() - start_time)

answered May 17 '16 at 05:47

gbin

2,960
1
14
11

On my computer the original responds: 76576500 16.701260805130005 The optimized one: 76576500 4.333745718002319 – gbin May 17 '16 at 05:50
Pardon me, but I did not understand your code below the 11the line (excluding the blank lines). Why did you write that if the object is a perfect square then return 2. By this logic, an input of 16 (which is a perfect square) would result in an output of 2 which is obviously not true since 16 has 5 factors (1 ,2 , 4, 8, 16). Kindly back up your logic with suitable explanation. – Aradhye Agarwal May 17 '16 at 06:47

How to make my program more efficient in Python

1 Answers1