Need help optimizing solution for Project Euler problem #12.

Question

Hey everyone,

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

  48
 /  \
2   24
   /  \
  2   12
     /  \
    2   06
       /  \
      2    3 

Knowing this, we construct the formula d(48) = (4+1)(1+1) [d(n) = (a+1)(b+1)(c+1)...] to determine that 48 has 10 factors.

d(n)  = (a+1)(b+1)(c+1)...
d(48) = (4+1)(1+1)
d(48) = (5)(2)
d(48) = 10

.

How can I optimize my code? Are these formulas the best solution? I feel that finding all the prime factors, then implementing the formulas would take longer than the program that I already have in place.

Many thanks,

Justian

EDIT:

Before anyone starts posting links, I have looked around similar questions in SO without any luck - I just can't think up implementations of their methods that would run quicker than what I already have in place.

EDIT2:

My 2nd attempt at the Sieve of Eratosthenes (for Problem 10):

int p = 3, n = 2000000;
long total = 0;
boolean[] sieve = new boolean[n];

for (int i = 3; i < n; i += 2)
    sieve[i] = true;

sieve[2] = true;

while (p * p < n) {
    for (int i = p; i < n; i++)
        if (sieve[i] && (i % p) == 0)
            sieve[i] = false;
    p++;

    while (!sieve[p])
        p++;
}

for (int i = 0; i < n; i++)
    if (sieve[i])
        total += i;

System.out.println(total);

Runs at ~985.399 ms - not too much faster than other method, but hasn't been optimized yet. It works, however.

Answer 1

Have you considered breaking into prime factors, and keeping track of the primes so you don't have to recalculate them?

Answer 2

Use the underlying mathematical structure, this will dramatically change your program's running time. This also applies to problem 10, by the way; if you can't do it in a few milliseconds, you've used a massively inefficient algorithm. In fact, I advise you to work on problem 10 first, because problem 12 builds on it.

I'm going to give a better algorithm for problem 12 below, but first, here's an observation that should speed up your program significantly. If two numbers x and y are coprime (i.e. they have no common divisor other than 1), then d(x·y) = d(x)·d(y). In particular, for a triangle number, d(n·(n+1)) = d(n)·d(n+1). So instead of iterating over the triangle numbers n·(n+1), iterate over n: this will significantly reduce the size of the arguments passed to d(n).

If you do that optimization, you'll notice that you compute d(n) twice in a row (once as d((n-1)+1) and once as d(n)). This suggests that caching the result of d is a good idea. The algorithm below does it, but also computes d bottom-up rather than top-down, which is more efficient because multiplying is a lot faster than factoring.

---

Problem 10 can be solved by a simple application of the sieve of Eratosthenes. Fill up an array of booleans (i.e., a bit vector) of size 2000000 such that with sieve[i]==true if i is prime; then sum up the numbers for which sieve[i]==true.

Problem 12 can be solved by a generalization of the sieve of Eratosthenes. Instead of making sieve[i] a boolean indicating whether i is prime, make it a number indicating the number of ways in which it is non-prime, i.e. the number of divisors of i. It is easy to modify the basic sieve of Eratosthenes to do that: rather than set sieve[x*y] to false, add 1 to it.

Several subsequent project Euler problems benefit from a similar approach.

One issue you may have is that in problem 12, it's not clear when to stop computing the sieve. You can go two ways about it:
1. compute the sieve by chunks on demand, a worthwhile programming exercise in itself (this will require more complex code that the second method)
2. or start by overestimating a bound: find some triangle number that has over 500 divisors, you know you'll stop before or at that number.

You can gain more time if you realize that you only need to care about odd numbers, since d(2^k·n) = (k+1)·d(n) if n is odd, and finding k and n given only (2^k·n) is fast on a binary computer. I'll leave the details of that optimization as an exercise.

Answer 3

I did this one a while ago, so I don't remember all of the optimizations, here are some:

1. use summation formula for sum(1...n)
2. find prime factors with methods described in problem 7 and problem 10
3. determine how many divisors n has based on its prime factorization*

*Treat this as a probability question if you don't know the "rule". E.g., you have four flavour-shots you can add to your coffee, how many options do you have?