Project Euler Problem #12 - Highly Divisible Triangular Number (in Java)

The main concept of this algorithm is decreasing the time it takes to complete. Using brute force (checking all numbers from 1 to n, or even 1 to n/2) will absolutely not work. Your program will not finish.

What I've done is only checked numbers from 1 to sqrt(n), which helps an incredible amount. In fact, it reduces the time to about 400 milliseconds (less than half of a second). The following code produces the output in that amount of time, however if you were to use n as a long type and/or then also have the triangleNumber method return a long, the time would increase to about 1000 milliseconds (about 1 second). I just thought that was interesting and I originally started with that, however once I found out that the answer was in range of the int maximum value, I altered the code to be in terms of an int to save some time.

To put the restriction of the square root of the number into perspective, let's say we were dealing with a number that was 2 million (close to the actual answer). The square root of 2 million is about 1400, which means instead of 2 million iterations, we only have a thousand. That compounded to every number that's being tested saves an incredible amount of iterations, and therefore, time.

All of the factors from 1 to the square root of a number contain exactly one half of all the factors of that number. So, you only need to test from 1 to sqrt(n) and then multiply that result by 2 to count the other corresponding half of the factors.

All of the factors that are less than the square root of the number directly correspond to the other half of the factors. That means that a factor from the first half has to be multiplied by its corresponding factor from the second half to result in the final number.

/*
    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?
*/

public class Problem_12_Highly_Divisible_Triangular_Number {

    /* returns the nth triangle number; that is, the sum of all the natural numbers less than, or equal to, n */
    public static int triangleNumber(int n) {
        int sum = 0;
        for (int i = 0; i <= n; i++)
            sum += i;
        return sum;
    }

    public static void main(String[] args) {

        long start = System.currentTimeMillis(); // start the stopwatch
        
        int j = 0; // j represents the jth triangle number
        int n = 0; // n represents the triangle number corresponding to j
        int numberOfDivisors = 0; // number of divisors for triangle number n
        
        while (numberOfDivisors <= 500) {

            // resets numberOfDivisors because it's now checking a new triangle number
            // and also sets n to be the next triangle number
            numberOfDivisors = 0;
            j++;
            n = triangleNumber(j);
            
            // for every number from 1 to the square root of this triangle number,
            // count the number of divisors
            for (int i = 1; i <= Math.sqrt(n); i++)
                if (n % i == 0)
                    numberOfDivisors++;
            
            // 1 to the square root of the number holds exactly half of the divisors
            // so multiply it by 2 to include the other corresponding half
            numberOfDivisors *= 2;
        }
        
        long finish = System.currentTimeMillis(); // stop the stopwatch
        
        System.out.println(n);
        System.out.println("Time taken: " + (finish - start) + " milliseconds");
    }
}
DOWNLOAD

          Created: March 7, 2014
Completed in full by: Michael Yaworski