Project Euler Problem 12 - triangle number with 500 divisors I've just done Problem 12 of Project Euler:


  What is the value of the first triangle number to have over five hundred divisors?
  
  The \$N\$'th triangle number is the sum of all natural numbers from \$1\$ to \$N\$, for example, the 5th triangle number is \$1 + 2 + 3 + 4 + 5 = 15\$


I get the correct answer in around 2.5 seconds.

I was wondering if anyone could suggest anything that could improve the performance of the program, or improve the code in general.

public class Problem12 {

public static void main(String[] args) {
    double startTime = System.currentTimeMillis();
    run();
    double endTime = System.currentTimeMillis();
    System.out.println("Took "+((endTime - startTime) / 1000)+" seconds"); 
}

public static void run() {
    boolean go = true;
    long number = 1;
    long nextNum = 2;
    int maxDivisors = 500;
    while (go) {
        if (countDivisors(number) &gt; maxDivisors) {
            System.out.println("The first triangle number with over "+maxDivisors+" divisors is: "+number);
            go = false;
        }
        else {
            number += nextNum;
            nextNum++;
        }
    }
}

public static long countDivisors(long number) {
    long divisors = 0;
    for (int i = 1; i*i &lt;= number; i++) {
        if (number % i == 0) {
            divisors+=2;
        }
    }
    return divisors;
}
}
There is an error in your countDivisors() function, the result is one too large
for a perfect square, i.e. countDivisors(25) returns 4 instead of 3.
Also the loop variable i should be a long to avoid an integer overflow
when testing i*i &lt;= number.
 A correct version would be

public static long countDivisors(long number) {
    long divisors = 0;
    for (long i = 1; i*i &lt;= number; i++) {
        if (number % i == 0) {
            if (i*i &lt; number) {
                divisors += 2; // i and number/i are (different) divisors
            } else {
                divisors += 1; // i == number/i is a divisor
            }
        }
    }
    return divisors;
}


The run() function can be simplified slightly, the boolean go variable
is not really necessary:

public static void run() {
    long number = 1;
    long nextNum = 2;
    int maxDivisors = 500;
    while (countDivisors(number) &lt;= maxDivisors) {
        number += nextNum;
        nextNum++;
    }
    System.out.println("The first triangle number with over "+maxDivisors+" divisors is: "+number);
}


To improve the performance, use the fact that


triangle numbers are of the form \$ n \, (n+1)/2  \$, and
the "number-of-divisors function" \$ \sigma_0(n) \$ is multiplicative,
i.e. \$ \sigma_0(m \, n) =  \sigma_0(m) \, \sigma_0(n) \$ if \$ m, n \$
are relative prime (see Divisor Function).


If \$ n \$ is even then \$ n/2 \$ and \$ n+1 \$ are relative prime,
and if \$ n \$  is odd then \$ n \$  and \$ (n+1)/2 \$ are relative prime.
This leads to the following implementation

public static void run() {
    long n = 1;
    int maxDivisors = 500;
    while (countDivisors((n+1)/2) * countDivisors(n) &lt;= maxDivisors) {
        n++;
        if (countDivisors(n/2) * countDivisors(n+1) &gt; maxDivisors) {
            break;
        }
        n++;
    }
    long number = n*(n+1)/2;
    System.out.println("The first triangle number with over "+maxDivisors+" divisors is: "+number);
}


which is faster because the countDivisors() function is called with smaller
numbers. On my computer it reduces the time from 0.6 to 0.02 seconds.

A faster implementation of countDivisors() would use the prime
factorisation of the given number, as explained in the above referenced
Wikipedia article.