# Triangle numbers

Published on 2011-07-24Project Euler problem 12 asks the reader to find the smallest triangle number that can be evenly divided by over 500 numbers:

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?

After futzing a bit with primes and square roots, I gave up and wrote a naive solution and then optimized how it determined the number of divisors a given number had. The vast majority of numbers have an even number of divisors, as if `a`

/`b`

= `c`

, then both `b`

and `c`

are divisors, one of which is less than the square root of `a`

, the other greater. Perfect squares are the exception to this rule, as they have not only paired divisors but also a whole number square root. By only checking for divisors up to a number's square root, the code runs much faster than a truly naive solution, which would simply check if all numbers 1-`a`

were divisors of `a`

.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem12 { class Program { static void Main(string[] args) { int triangle = 1; int numOfDivisors = 0; for (int i = 2; ; i++) { triangle += i; for (int j = 1; j < triangle; j++) { if (triangle % j == 0) numOfDivisors += 2; if (j == Math.Sqrt(triangle)) numOfDivisors++; if (numOfDivisors > 500) goto Answer; if (j > Math.Sqrt(triangle)) break; } numOfDivisors = 0; } Answer: Console.WriteLine("The smallest triangle number with over 500 divisors is {0}", triangle); } } }