Project Euler Problem 12 Solution

Problem Link

Problem Statement
Find the smallest triangle number which has more than 500 divisors.First few triangle numbers are 1,3,6,10,15




Solution

Idea 1:(brute force-time 0.629)
C++ implementation

#include <stdio.h>
#include <math.h>

long numberOfDiv(long n)
{
	if(n == 1)return 1;
	long n_div = 2;

	long max = sqrt(n + 1);

	for(long i = 2; i < max; i++)
		if(n % i == 0)
			n_div += 2;

	return n_div;
}

int main(){
	long i,j,k,l,n_div,n;
	__int64 triangle;

	n = 1;
	triangle = 1;

	while(numberOfDiv(triangle) <= 500)
	{
		triangle += ++n;
	}
	printf("%I64d\n",triangle);


	return 0;
}