4
\$\begingroup\$

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.

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

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.

\$\endgroup\$
2
\$\begingroup\$

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
# (...)
\$\endgroup\$
2
\$\begingroup\$

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.