# Finding number of divisors faster

Here is my code:

triangle_numbers = []
number = 0
for i in range(0, 10000):
number = number+i
triangle_numbers.append(number)

for number in triangle_numbers:
number_of_divisors = 1
for i in range(1, int(number/2)+1):
if number % i == 0:
number_of_divisors = number_of_divisors + 1
if number_of_divisors > 500:
print("FOUND AT ", number)


It takes forever to return the answer. How do I make it faster? I'm a beginner, so if you could walk me through your answer that would be great!

The challenge that I am doing is Highly divisible triangular number - Problem 12.

• You might want to have a look at previous Q&A's about the same problem. – Martin R Jun 3 '17 at 18:51

You are searching for a number with more than 500 divisors in the range 0 to 10000. But we are not sure whether a number less than 10000 will be the required number. So, instead of searching a number in a range, we can search for that number which satisfies the condition the in the set of positive real numbers.

num=1
tnum=0 #representing triangular number
nof=0
while nof<501:
nof=2 #to include 1 and the number itself
tnum+=num
num+=1
for i in range (2,int((tnum/2))+1):
if tnum%i==0:
nof+=1
print (tnum," : ",nof) #printing the triangular number and its number of divisors
print ("Required number is ", tnum)


This code will also take a good amount of time to get you result.

Not a true answer to your question (regarding performance), but here's two things to think about:

• range() will, if called with one argument, assume 0 as first argument, so there's no need to explicitly call range(0, x).

• There's a more pythonic way of adding any type x and y together: x += y

And other operations on x and y include:

x -= y    # Instead of x = x - y
x *= y    # Instead of x = x * y
# (...)


Instead of trying every number less than N/2 you should use fundamental theorem of arithematic and reduce N = (p1 ^ a1) * (p2 ^ a2) ... (pn ^ an) then total divisors will be tau(N) = (1 + a1) * (1 + a2) ... (1 + an)

• Load primes (Generate using a seive or read a file)
• For each number take primes pi less than N and find ai
• Take product after adding one