5
\$\begingroup\$

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);
    }
}
\$\endgroup\$
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you very much for your time and effort. Great explanation and advice also. :) \$\endgroup\$ – kfcobrien Dec 2 '14 at 0:53
  • 1
    \$\begingroup\$ Woah never knew Java's optimizations with its JIT compilation limited the optimizations within main. \$\endgroup\$ – Qix - MONICA WAS MISTREATED Dec 2 '14 at 1:02
  • \$\begingroup\$ rolfl just a quick question, would you be able to point me to a similar site to Project Eular.... Maybe something that takes steps a little slower and isn't so dependent on knowing complex algorithms. Would really appreciate it as I love practicing. Thank you guru rolfl :) \$\endgroup\$ – kfcobrien Dec 2 '14 at 1:41
  • 1
    \$\begingroup\$ Of all the 'challenge' sites out there, I prefer Project Euler. Other sites are even less friendly when it comes to having problems... My suggestion is for you to continue with finding problems, and to use Code Review as part of your learning experience ;-) \$\endgroup\$ – rolfl Dec 2 '14 at 1:49
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.