So there was I, tinkin.
And I thought maybe others would like to think a bit too
It's from projecteuler.net. It's one of the "easier" ones, it's not actually about writing something that works. That's not tough. It's about writing something that works and solves it within a reasonable amount of time (preferably seconds, not days!).
Quote:
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?
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?
No, the actual problem isn't that hard per say, you can simply brute force it to find the number. But brute force = bad.
So, trying to come up with an elegant method of doing this, so it solves within the shortest time possible. A starter...
Firstly we have to work all the "triangle numbers" or whatever. Just do a never-ending loop...
Code:
int sum = 0;
int i = 1;
while(true){
}
int i = 1;
while(true){
}
Sum? That'll just be a simple sum to get the "triangle" number.
i is representing the ith number
so inside something along the lines of
Code:
sum += i;
to keep track of our "triangle number", course, we need to increment i. Completing it a bit...
Code:
int sum = 0;
int i = 1;
while(true){
sum += i;
if(divisors(sum) >= 500){
System.out.println(sum);
break;
}
i++;
}
int i = 1;
while(true){
sum += i;
if(divisors(sum) >= 500){
System.out.println(sum);
break;
}
i++;
}
The if statement is merely calling a method "divisors" which will return the number of divisors that the number has. If it's more than 500, print it and exit.
So what are some solutions for it? Elegance over brute force preferred
The code I wrote took 1.79 seconds to find the answer, however someone else has solved it with a different solution in 94ms (mine is 1719ms!)
Give it a go, how long did it take and what was the answer and your code?
Fastest seen on the actual problem is in the solution paper, which is as follows:
Quote:
Written in assembly and
almost fully optimized, it runs in less than 1 millisec on a P4-1500. It should easily run in less
than 10 millisec when written in most modern compiled languages.
almost fully optimized, it runs in less than 1 millisec on a P4-1500. It should easily run in less
than 10 millisec when written in most modern compiled languages.
Bugger!
I think the numfactors I can include optimise by just having a running total of exponents in prime_factor
Mine still swish around in there 
