I've been having my fun with Project Euler challenges again and I've noticed that my solution for number 12 is one of my slowest at ~593.275 ms per runthrough. This is second to my solution for number 10 at ~1254.593 ms per runthrough. All of my other answers take less than 3 ms to run with most well under 1 ms.
My Java solution for Problem 12:
main():
int index = 1;
long currTriangleNum = 1;
while (numDivisors(currTriangleNum) <= 500) {
index++;
currTriangleNum += index;
}
System.out.println(currTriangleNum);
numDivisors():
public static int numDivisors(long num) {
int numTotal = 0;
if (num > 1)
if (num % 2 == 0) {
for (long i = 1; i * i <= num; i++)
if (num % i == 0)
numTotal+=2;
} else {
// halves the time for odd numbers
for (long i = 1; i * i <= num; i+=2)
if (num % i == 0)
numTotal+=2;
}
else if (num == 0)
return 0;
else if (num == 1)
return 1;
else (num < 0)
return numDivisors(num *= -1);
return numTotal;
}
.
Looking around the solutions forum, some people found that these formulas (n = (p^a)(q^b)(r^c)... & d(n) = (a+1)(b+1)(c+1)...) worked for them, but I personally don't see how it'd be any faster; faster by hand, perhaps, but not in a program.
.
The basic thought process is as follows:
We want to calculate the number of divisors in 48. By looking at the factor tree below, we can conclude that 48 = (2^4)(3^1) [n = (p^a)(q^b)(r^c)...].