Finding number of divisors faster

Question

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.

• Martin R: You might want to have a look at previous Q&A's about the same problem.

Answer 1

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.

Answer 2

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

Answer 3

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
# (...)