Gerry Heidenreich

Thanks to Mr. Payne, I've been spending more hours awake coding, and less time sleeping, in the name of 'fun and recreation'...

As Damon points out in his esoteric and colorful post yesterday, I've been working my way through the Euler (prounounced 'oy ler!) puzzles at Project Euler.  I've banged out solutions for puzzles 1-13, but #10 is the only one I can't get under 1 minute (In fact, it's the only one that isn't solved almost instantly). 

Problem 12 is interesting: Which is the first triangle number to have over 500 divisors?

Finding triangle numbers is trivial; the actual challenge in this puzzle is efficiently counting divisors for increasingly huge numbers.

The initial approach that almost works:
For number n, iterate from 1 to n, increment divisorCount where i % n ==  0
(Once you try this out, you will find that with this approach, your highest divisor count will quickly reach 320 divisors, and will ultimately hang at around 480 before it starts to crawl...)

Finding the first triangle number to have over 1000 divisors, in under 10 seconds:
When things get even slightly complex, I turn to pen & paper... within minutes I saw the pattern I was looking for.  The following method will return a list of divisors for an int:

static List<int> GetDivisors(int num) {
   List<int> divisors = new List<int>();
   int divisorCandidate = 1;
   int multiple = 1;
   do {
      if (num % divisorCandidate == 0) {
         multiple = num / divisorCandidate;
         divisors.Add(divisorCandidate);
         //for squares, divisorCandidate == multiple (3*3=9 etc), so only count it once
         if (divisorCandidate < multiple) divisors.Add(multiple); 
      }
      divisorCandidate++;
   } while (divisorCandidate < multiple);
   divisors.Sort();
   return divisors;
}

I doubt it's even remotely useful in production, but this method is a great example of how a little analysis of the problem (especially away from the keyboard) can result in a much more elegant solution to your problem than brute force.