Triangle number with 500 divisors

Question

It should work but my comp can't compute it in time. It is Project Euler problem 12. Just a small bit of advice would be nice. Only at this a short time so I probably just haven't learned a good way to manipulate the situation yet.

public class HighlyDivisibleTriangularNumber{
    public static void main(String args[]){
        long count = 1, sum = 0, i;
        for(i = 1; count != 500; i++){
            sum += i;
            if(sum % 2 == 0 && sum % 3 == 0) count = 3;
            else count = 2;
            for(int j = 4; j <= sum/2; j++)
                if(sum % j == 0) count++;
        }
        System.out.println(i-1);
    }
}

Answer 1

Java is a just-in-time compiled language. As a side-effect of this, it is common for performance problems to happen when you have all the code in the main method. The reason is that Java often only compiles methods that are called very often, but the main method is only called once, so it is not compiled optimally.

This is one reason why 'function extraction' is often suggested (as well as the other benefits like readability).

So, consider a method that's called 'countDivisors':

private static long countDivisors(long value) {
    long count = 1;
    for (long i = 1; i <= value/2; i++) {
        if (value % i == 0) {
            count++;
        }
    }
    return count;
}

This code will be called often, and will thus be compiled optimally.

The main method also becomes simpler, with:

public static void main(String args[]){
    long count = 1, sum = 0, i = 0;
    do {
        i++;
        sum += i
        count = countDivisors(sum);
    } while (count < 500);
    System.out.println(i);
}

Now, whether this improves the performance enough, is uncertain, but it is more readable, and will be faster.

There's probably a smarter way to do this too, a better algorithm is normally what's required with Euler problems.

Answer 2

better algorithm is normally what's required with Euler problems

This is exactly what is going on here. ProjectEuler is about math; programming is just a side effect.

To give you a feeling of what has to be done here:

• Realize that triangular numbers are the sum of a particular arithmetic progression, hence they can be represented as a product of 2 integers.

• Prove (at least to yourself) that those integers are coprime.

• Prove (at least to yourself) that a number of divisors is a multiplicative function.

• Combine all that knowledge into an efficient algorithm.

Only then you may start coding.