need fast algorithm that checks the amount of divisors.

at this moment i have an algorithm but it is very slow. i need it for project euler #12 http://projecteuler.net/problem=12
what i have to do is:
The sequence of triangle numbers is generated by adding the natural numbers. So the 7th 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?


this is my code now: but it takes too long untill he got the answer. so could anyone give me an faster algorithm.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <cmath>

int amount_of_divisors(long unsigned long x) {
	int divisors=0;
	for (int i=x;i>0;i--) {
		if (x%i==0) { 
			divisors++;
		}
	}
	return divisors;
}

int main() {
	for (int n=7;;n++) {
		long unsigned long trianglenumber=(n*(n+1))/2;
		int divisors=amount_of_divisors(trianglenumber);
		if(divisors>500) {
			std::cout<<trianglenumber<<std::endl;
			break;
		}
		std::cout<<divisors<<std::endl;
	}
	system("pause");
	return 0;
}
found the problem. the loop was going from x to 1 instead of 1 to sqrt(x). takes alot of time i quess.
this code worked in 2 seconds.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cmath>
#include <stdio.h>
#include <time.h>

int amount_of_divisors(long unsigned long x) {
	int divisors=0;
	for (int i=1;i<=sqrt(double(x));i++) {
		if (x%i==0) { 
			divisors+=2;
		}
	}
	return divisors;
}

int main() {
	clock_t start, end;
	start = clock();
	for (int n=2015;;n++) {
		long unsigned long trianglenumber=(n*(n+1))/2;
		int divisors=amount_of_divisors(trianglenumber);
		if(divisors>500) {
			std::cout<<trianglenumber<<std::endl;
			break;
		}
	}
	end = clock();
	printf("\nTook %f seconds\n", (double)(end-start)/CLOCKS_PER_SEC);
	system("pause");
	return 0;
}
Topic archived. No new replies allowed.