This challenge wants you to return the first triangular number that has over 500 factors. This challenge was a 2 part, first you have to be able to calculate out a "triangular number" which they define as a natural number added upon itself (similar to Fibonacci numbers) so that the 7th number in the series would be 1+2+3+4+5+6+7 or 28. The second part is being able to quickly calculate all the factors of a number. This was relatively straight forward, so I'll just post the code, there are comments in certain areas as to why I chose to do it like I did.
Program.cs
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace ProjectEuler_12
{
internal class Program
{
private static HashSet GetMultiples(long num)
{
// use a hashset to guarantee uniqueness
HashSet multiples = new HashSet { 1L, num };
long root = (long)Math.Sqrt(num);
// we only need to loop up to the square root of the num
// because we're getting both the low and high factor of the num at once
// no number could be higher than root*root
for (long i = 2; i <= root; i++)
{
if (num % i == 0)
{
multiples.Add(i);
multiples.Add(num / i);
}
}
return multiples;
}
private static void Main(string[] args)
{
IEnumerable triangularNumbers = TriangularNumberGenerator();
int multipleCount = 0;
using (var enumerator = triangularNumbers.GetEnumerator())
{
long count = 0;
long highestMultipleCountAchieved = 0;
while (multipleCount < 500)
{
enumerator.MoveNext();
count++;
multipleCount = GetMultiples(enumerator.Current).Count;
if (multipleCount > highestMultipleCountAchieved)
{
highestMultipleCountAchieved = multipleCount;
Debug.WriteLine("Number: {2}, Index: {0}, Multiple Count: {1}", count, highestMultipleCountAchieved, enumerator.Current);
}
}
Console.WriteLine("First triangular number index to have 500 multiples: {0}\r\nTriangular Number: {1}", count, enumerator.Current);
}
}
/// <summary>
/// The sequence of triangle numbers is generated by adding the natural numbers.
/// </summary>
/// <returns></returns>
private static IEnumerable TriangularNumberGenerator()
{
long prevNum = 0;
long sum = 0;
while (true)
{
sum += ++prevNum;
// use of yield return lets us go up as high as we need and only
// as high as we need in this infinite series
yield return sum;
}
}
}
}