patternjavaModerate

Project Euler Problem 12 - triangle number with 500 divisors

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

problemnumberwithtriangleproject500eulerdivisors

Problem

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) > 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 <= number; i++) {
        if (number % i == 0) {
            divisors+=2;
        }
    }
    return divisors;
}
}

Solution

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 

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)  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.

Code Snippets

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

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

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

Context

StackExchange Code Review Q#74895, answer score: 14

Revisions (0)

No revisions yet.