Project Euler is great. The first problems are much easier to solve than any other programming-oriented problem-solving website I’ve yet to come across, but there are plenty of problems available (400+ as of this writing), and the difficulty does increase.
I will never post the answer to a Project Euler problem on this site. They explicitly request that people not post answers, and I will honor that. However, I may attempt, from time to time, to point in a few directions to help people create their own answer. This post is about problem 12, the Highly Divisible Triangular Number.
A triangle number is found by adding all the numbers from 1 to n. So the 4th triangle number would be 1 + 2 + 3 + 4, or 10. The problem asks us to find the first triangle number that has over 500 divisors. This problem can be broken done thusly:
- Find triangle numbers
- Find divisors of numbers
- Combine
My initial idea was brute force with a few for loops. However, I quickly saw a pattern in the triangle numbers that I was able to write into 2 short algorithms, depending on if the number (n) was odd or even (find the pattern for yourself, I’m sure you can).
After doing that, it was just a matter of finding a reasonably quick way to find the factors of a number. I was unable to understand Pollard’s rho algorithm, so I had to stick with what I already knew, and that is:
- All numbers (n) have an even amount of divisors,
- half of those divisors are less than the square root of n, and
- the other half are greater than the square root of n
That allowed me to write a for loop that checked all the divisors of n in a reasonable amount of time. To explain #2-3 above, let’s take the number 30. The divisors of 30 are: 1, 2, 3, 5, 6, 10, 15, and 30. The square root of 30 is roughly 5.47, so to find the amount of divisors of 30, we only need to find the amount of divisors up to 5. There are 4 divisors up to 5: 1, 2, 3, and 5. Therefore, 30 has 4 x 2 divisors, or 8 divisors. You can do a little tweaking of this to find the exact divisors of a number, not just the exact amount of divisors, and I encourage you to figure that out for yourself.
TECHibid 