Problem 12 Project Euler Solution with python

Update: I have tried breaking numbers method but it is not as efficient as the program which we have written. It is useful when you will use it for finding divisors of a number.

Highly divisible triangular number

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th 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?

To solve this problem we will be using a code snippet from Problem 3 which we have solved earlier. I will first share with you the code snippet and the concept behind our program solution so that it will be easy for you to decode the code.

#A dictionary to store the powers of primes
dic = {}
#Starting with a prime number 2
i = 2
#for loop to factor a number
while i <= triangle_number:
 #If 'i' divides the number, then it is a
 #prime factor 
 if triangle_number % i == 0:
  #Changing the value of number so that
  #we will not divide it with the same
  #number again and again
  triangle_number = triangle_number/i
  #We are storing the value in terms 
  #of power of the prime number in dict
  if i in dic:
   dic[i] += 1
  else:
   dic[i] = 1
  i = i-1
 i += 1

The above factorization technique is based on Method 2 atHow to Factor a number .
The code is well commented again.

Now to understand the program which we have written to solve problem 12, you will have to give a quick glance through these links:

1. How many divisors does 138600 have?
2. How to determine number of divisors of an integer
3. 1+2+3+4+.. Wiki
4. Python Multiply all items in a list together
5. Efficient method to check if key exists in dictionary

That's it you are done. You are ready for takeoff 😋.

Program

Program is a follows:
 
The code is well commented again and I don't think it requires explanation. I suggest you to check out the links if you haven't yet.

I just want to share one thing. Instead of using dic in the code you could append all the divisors to a list and then find each instance of the prime number in the list. To accomplish this you will need sets in python. I have given you one hint, now try to write the program. It will be fun.

If you want to download the program you can do it from Github Gist

Output

Answer: 76576500
Execution time: 3.29955482483 seconds
Output:

Problem 12 Project Euler Output

Project Euler Problem 12 with solution

Summary

This problem was not really challenging, but it required a very good algorithm. As we have already solved problem 3 our program became more simple. But it had execution time greater than 1second, which I was not satisfied. But I was not able to think of another solution. I know that we are looping a lot of times but I couldn't come up with a better solution. But I promise you that if I will find a better solution then I will for sure post it.

I found a solution but I am not sure if it will work faster than the above code. If you have a better solution then please do share it with me.

If you haven't understood anything in this post then please do comment in the comment box below and I will be glad to help you.

Please do comment in the comment box if you have found any typo or want me to add anything to improve this post.

You can also contact me if you want to.

Thank you. Have a nice day😃.