Efficient algorithm for triangle numbers

[george61]

In these problem I have to find triangular number by the number of it's divisors. The program takes about 0.65 seconds to find the first triangular number with >100 divisors and about 87 seconds for the number with >200 divisors which means that my algorithm is very inefficient. Any help for making this program working faster will be greatly appreciated.

#include <stdio.h>
#include <time.h>
void factors()
{
	int first = 1;
	int triangle = 0;
	int count = 0;
	//Start measuring
	clock_t start, end;
	start = clock();
	for(int i=0; i<100000; i++)
		{triangle = first + triangle;
		first++;
		count = 0;
			for(int j=1; j<=triangle; j++)
				{if((triangle % j)==0)
					count++;
			}
		if(count>100)
			{printf("\n%d:",triangle);
			printf(" |%d divisors",count);
			end = clock();
			printf("\nTook %f seconds\n", (double)(end-start)/CLOCKS_PER_SEC);
			break;}
		}
}
int main(){
	factors();
	return 0;
}

[Momerath]

Well, divisors always come in pairs, so you only need to search up to the square root of the number (and add 2 to the divisor count each time you find one).

To give you an idea of how much of a speed improvement, I wrote your routine and the improved one in C# (it's what I do mainly). In debug mode I get these results:

2031120: |240 divisors - Took 41116 milliseconds (Original)
2031120: |240 divisors - Took 25 milliseconds (Square Root)

That's 41 seconds compared to 0.025 seconds.

And as you can see, that's for the > 200 divisors.