Project Euler #5 in Java

Project Euler #5:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Here is my solution:

class SmallestMultiple {
    
    private static final int MAX = 20;

    public static void main(String[] args) {
        long time = System.nanoTime();
        int result = 1;
        for(int i = 1; i <= MAX; i++) {
            result = smallestMultiple(result, i);
        }
        time = System.nanoTime() - time;
        System.out.println("Result: " + result + "\nTime used to calculate in nanoseconds: " + time);
    }

    private static int smallestMultiple(int i, int j) {
        for(int index = 2; index <= i && index <= j; index++) {
            if(i % index == 0 && j % index == 0) {
                i /= index;
            }
        }
        return i * j;
    }

}

Output:

Result: 232792560

Time used to calculate in nanoseconds: 11603

Questions:

• Is is as efficient as it can be? If not, how can I improve it?

• Does it smell?

Mathematically, the least common multiple of a range of numbers can be expressed as

$$LCM(1..1) = 1$$
$$LCM(1..n+1) = \frac{LCM(1..n) * (n+1)}{GCD(\;LCM(1..n), \;n+1)} $$

So you can start with 1 and work your way up

static long leastCommonMultiple(long n) {
    long multiple = 1;

    for ( long i = 1; i <= n; i++ ) {
        multiple *= i / gcd(multiple, i);
    }

    return multiple;
}

The optimal Greatest Common Divisor algorithm is

static long gcd(long a, long b) {
    return ( 0 == b ) ? a : gcd(b, a%b);
}

The iterative version is

static long gcd(long a, long b) {
    while ( 0 != b ) {
        long temp = a;
        a = b;
        b = temp % b;
    }

    return a;
}

Running with the iterative version takes about a third of the time that your solution does on my machine.

You can get an additional speedup by using the fact that you already know \$LCM(1..10) = 2520\$.

static long leastCommonMultiple(long n) {
    long multiple = 2520;

    for ( long i = 11; i <= n; i++ ) {
        multiple *= i / gcd(multiple, i);
    }

    return multiple;
}

That allows you to start at 11 rather than 1. It's not much of a gain though. And of course, it's unique to this particular problem.

StackExchange Code Review Q#78267, answer score: 6