Project Euler #5 (LCM of 1-20)

Challenge: 2520 is the smallest number divisible by 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by 1-20?

Solution:

public class Euler5 {
    public static void main(String[] args) {
        long startTime = System.nanoTime();
        int result = 0;

        for (int i = 2520; i > 0; i += 2520) {
            if (isSmallestMultiple(i)) {
                result = i;
                break;
            }
        }

        System.out.print("Result: " + result +
            ".\nTime used for calculation in nanoseconds: " +
            (System.nanoTime() - startTime) + ".");
    }

    public static boolean isSmallestMultiple(int i) {
        return i % 2 == 0 &&
            i % 3 == 0 &&
            i % 4 == 0 &&
            i % 5 == 0 &&
            i % 6 == 0 &&
            i % 7 == 0 &&
            i % 8 == 0 &&
            i % 9 == 0 &&
            i % 10 == 0 &&
            i % 11 == 0 &&
            i % 12 == 0 &&
            i % 13 == 0 &&
            i % 14 == 0 &&
            i % 15 == 0 &&
            i % 16 == 0 &&
            i % 17 == 0 &&
            i % 18 == 0 &&
            i % 19 == 0 &&
            i % 20 == 0;
    }
}

Example output:

Result: 232792560.
Time Used for Calculation in nanoseconds: 11561136.

This is the first thing I tried. I started with a "should work" sentiment, and now that it has, I feel like it's an exceptional case.

• Is incrementing by the given multiple, given its coverage of 1

through 10 more intuitive than I suspect? I'm wondering if this
situation is coincidental since they're not all primes.

• Is there any obvious way of making this even faster?

• Would this solution work for additional requirements? (i.e 1-25)

Your approach is.... accurate, but inefficient. I believe you already know that. You can search here on Code Review for alternate algorithms (I believe the most efficient algorithm is described in this answer by David Zhang (I see ILoveCoding has answered something similar).

But, I would like to address an obvious inefficiency here:

public static boolean isSmallestMultiple(int i) {
    return i % 2 == 0 &&
        i % 3 == 0 &&
        i % 4 == 0 &&
        i % 5 == 0 &&
        i % 6 == 0 &&
        i % 7 == 0 &&
        i % 8 == 0 &&
        i % 9 == 0 &&
        i % 10 == 0 &&
        i % 11 == 0 &&
        i % 12 == 0 &&
        i % 13 == 0 &&
        i % 14 == 0 &&
        i % 15 == 0 &&
        i % 16 == 0 &&
        i % 17 == 0 &&
        i % 18 == 0 &&
        i % 19 == 0 &&
        i % 20 == 0;
}

Right, you know that 4 is a multiple of 2.... so, why do you do:

`i % 2 == 0`

when you're also going to do:

`i % 4 == 0`

Similarly, why do 4 when you do 8, and 16?

If you do 16, then you've already also checked 8, 4, and 2.

At a minimum, if you're going to hard-code the values, at least hard-code the largest factors.... No need hard coding a value that has a larger multiple too in the tests:

public static boolean isSmallestMultiple(int i) {
    return
        i % 11 == 0 &&
        i % 12 == 0 &&
        i % 13 == 0 &&
        i % 14 == 0 &&
        i % 15 == 0 &&
        i % 16 == 0 &&
        i % 17 == 0 &&
        i % 18 == 0 &&
        i % 19 == 0 &&
        i % 20 == 0;
}

StackExchange Code Review Q#76962, answer score: 5