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)...].

 
Edit
Report