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;
}``````

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.20 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.