Project Euler #12 - C

Question:

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?

Solution:

It is pretty easy to see that triangle numbers are numbers that can be reached via a summation. Summations ( I previously wrote factorial... whoops!) are easily calculated using the forumula n*(n-1) / 2. The goal is to find the first summation that can be evenly divided by 500 or more divisors. The fastest way I could think of to achieve this was to use the square root of the calculated triangle number as an upper bound for a loop. Any integer below that square root that evenly divides the triangle number must have a corresponding integer above the square root to match. And obviously, the square root of a triangle number (any number for that matter) multiplied by itself equals the triangle number. 

Remember that 1 and the triangle number itself count so start with number of divisors 2. Then, loop from 2 through sqrt(number) and for each number that evenly divides in, add 2 to the number of divisors the number has. If the number has an integer square root, add 1 more. When the number of divisors exceeds 500, we break out and print the triangle.

And thats it! 

#include <stdio.h>
#include <math.h>
#define TARGET 500

int main (void)
{
int divisors = 2;
int i = 7;
int limit; 


unsigned int triangle = 28; 


while ( divisors <= TARGET )
{
divisors = 2; // reset: 1 and itself 
i++;


triangle += i; // thank you 7aka for correcting my oversight 
limit = sqrt(triangle); 

int j;


for (j = 2; j <= limit; j++)
{
if (!(triangle % j))
{
if (j == limit) // this is the square root so only add 1 to divisors
divisors++;
else
divisors += 2;
}
}
}


printf("The first triangle number with 500 or more divisors is %d\n", triangle);


return 1;
}