Project Euler #12 Java implementation

Question

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28 We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Here is my code :

package coderbyte;

public class Java {

    public static void main(String[] args) {

        long start = System.nanoTime();

        int number = 0;
        int index = 0;
        boolean found = false;

        while (!found) {
            int counter = 0;
            index++;
            number = index * (index + 1) / 2;
            for (int i = 1; i * i <= number; i++) {

                if (number % i == 0) {
                    counter = (number % i == i ? counter + 1 : counter + 2);
                    if (counter > 500) {
                        found = true;
                        break;
                    }
                }

            }

        }

        System.out.println(number);

        System.out.println(System.nanoTime() - start);
    }
}

Any tips on how to improve the runtime and possible shorten the code.

Answer 1

Your solution is not good as you use a single method, stuffing everything inside, with no order nor logic.

It must be rebuilt from scratch.

---

public class TriagularNumberWithManyDivisors {

Use long, descriptive names, Example is not acceptable by any standard.

static final int DIVISORS_WANTED = 500;

I may have fun running this code for any number of divisors and I really do not want to go haunting for a magic number to change inside the code.

public static int triangular(int n) {
    return n * (n + 1) / 2;
}

This is a function, a part of your program that does only one thing, the function name also serves as documentation.

public static int divisors(int n) {
    int counter = 0;
    int limit = (int) Math.sqrt(n);
    for (int i = 1; i <= limit; i++) {
        if (n % i == 0) {
            counter += (n % i == i ?  1 : 2);
        }
    }
    return counter;
}

The code for counting divisors was kinda mixed in the main loop, and you had to pay the cost for not extracting it to a function in terms of an ugly boolean flag and two nested loops.

public static void main(String[] args) {
    for (int i = 0; true ; i++) {
        if (divisors(triangular(i)) > DIVISORS_WANTED) {
            System.out.println(triangular(i));
            break;
        }
    }
}

The main method, it is incredibly trivial to understand what this does now. It calls the others methods in a high level fashion, highlighting the algorithm.

Answer 2

Improving runtime

As with any Project Euler problems you have to invest in math. This particular problem requires understanding of the following:

• number of divisors is multiplicative: \$\sigma(nm) = \sigma(n) \sigma(m)\$ for coprime \$n, m\$.

• sequential numbers (such as index and index + 1) are coprime

• Therefore, instead of factoring index * (index + 1)/2 you should factor index and index + 1 independently. Not only each of them is much smaller than the number you are currently factoring, but you may reuse the factorization: index + 1 becomes index of the next iteration. Division by 2 slightly complicates the process.