The good lads at Project Euler present to me another brute force challenge! At least this will be easy to solve before I go to bed, albeit poorly and not optimized in the slightest.

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,28We 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?

Calculating the number of factors in any given number seems like a function that I will be requiring frequently throughout these problems so I decided to write a function for it in my Helper class. At the moment it is very slow and can be improved upon with prime factorization much like I’ve done in Problem 3 but I’m too tired at the moment to wrap my head around the concept again so this will have to do for now!

In my Helper class I added the following function:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
/// <summary> /// Returns the number of divisors of any given number /// </summary> /// <param name="number">How many divisors in this number</param> /// <returns>Number of divisors</returns> public int NumberOfDivisors(int number) { int numOfDivisors = 0; int sqrt = (int)Math.Sqrt(number); for (int i = 1; i <= sqrt; i++) { if (number % i == 0) { numOfDivisors += 2; } } //Correction if the number is a perfect square if (sqrt * sqrt == number) { numOfDivisors--; } return numOfDivisors; } |

The code is mostly straight forward to follow. It is important that we check for the square root of the number in this case instead of the full number however since I originally ran the program without the optimization in place before realizing it’s not going to complete within a reasonable time.

Calculating the triangle numbers in the Problem class was about as simple as it can get and by simply accessing the Helper function and using the following code I was able to process a solution to the problem in less than a second.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
using System; using System.Diagnostics; namespace ProjectEulerSolutions { /// <summary> /// </summary> class Problem012 { public void run() { var watch = Stopwatch.StartNew(); Helper MathHelper = new Helper(); int triangleNumber = 0; int i = 1; while (MathHelper.NumberOfDivisors(triangleNumber) < 500) { triangleNumber += i; i++; } Console.Out.WriteLine("The first triange number with atleast 500 divisors is: " + triangleNumber); watch.Stop(); var elapsedMs = watch.ElapsedMilliseconds; Console.Out.Write("Program completed in : " + elapsedMs + "ms"); } } } |

Honestly, I just wanted to knock off a problem for the day so I didn’t put too much effort into this like I should have so I may have to come back to this in the future and make it faster! That’s really all I have to say for now since it’s well past my bed time and I need to catch some ZZZzzz’s. Feel free to check out my GitHub for the full code solution and answers to these problems and other cool projects that I’m working on. Until next time good night, and sleep tight.