5
\$\begingroup\$

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.

  1. 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.
  2. Is there any obvious way of making this even faster?
  3. Would this solution work for additional requirements? (i.e 1-25)
\$\endgroup\$
3
  • 5
    \$\begingroup\$ project euler problems are better optimized by rethinking the algorithm itself rather than implementation. \$\endgroup\$ Jan 8 '15 at 12:30
  • 1
    \$\begingroup\$ Why don't you simply multiply 2520 by every prime number between 11 and 20, and then also by 2 (in order to make it divisible by 16, which "introduces an additional 2")? In other words, your number should be 2520*11*13*17*19*2. \$\endgroup\$ Jan 8 '15 at 12:35
  • \$\begingroup\$ Follow-up question \$\endgroup\$ Jan 9 '15 at 2:37
4
\$\begingroup\$
  1. for (int i = 2520; i > 0; i += 2520) and a break statement inside makes the logic of you code hard to follow. The questions are: what is 2520? It is a good practice to give magic constants some meaningful names. The second question is: what does i > 0 mean here? If you know that this condition always holds true, there is no need to keep it. You can either remove it or(even better) rewrite this piece of code using while loop:

    int result = 2520;
    while (!isSmallestMultiply(result))
        result += 2520;
    
  2. The isSmallestMultiple method could be implemented using a loop. That huge boolean expression is hard to read and it is unnecessary.

  3. The algorithm itself is pretty strange(it is not clear why it is correct(because of a magic constant 2520 in the first place), eventhough it is) and it is not efficient. A standard way to find an LCM of a group of numbers is to use the following fact: LCM(a0, a1, a2, ..., an) = LCM(LCM(a0, a1), a2, ..., an). Here is a simple and efficient implementation of it:

    public class Euler5 {
        final static int MAX_N = 20;
    
        static int gcd(int a, int b) {
            while (b != 0) {
                int t = a;
                a = b;
                b = t % b;
            }
            return a;
        }
    
        public static void main(String[] args) {
            int result = 1;
            for (int i = 1; i <= MAX_N; i++) {
                int currentGcd = gcd(i, result);
                result = result / currentGcd * i;
            }
            System.out.println(result);
        }
    }
    
\$\endgroup\$
5
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • \$\begingroup\$ Right, a lot of unnecessary checks on my part with this one. I've since fixed the unsightly inner method by looping from 11 <= 20, and checking if (n % i != 0) . I always attempt my first inclination...the simplest thing worked in this case, which stunned me enough to ignore how silly my method was. \$\endgroup\$
    – Legato
    Jan 8 '15 at 12:52
2
\$\begingroup\$

An alternative algorithmic solution:

You already know that 2520 is the LCM of 1 to 10. In order to expand it to be the LCM of 1 to 20, you can simply multiply it by every prime number between 11 and 20, and then also by 2 (in order to make it divisible by 16, which introduces that "additional factor").

A more generalized solution, is to iterate the new numbers (11 to 20), find the missing factor that each number introduces, and expand the LCM by that factor.

int result = 2520;
for (int i = 11; i <= 20; i++)
    result *= i/gcd(result,i);

A class that provides lcm and gcd methods:

public class MathUtil
{
    public static int lcm(int min,int max)
    {
        int result = 1;
        for (int i = min; i <= max; i++)
            result *= i/gcd(result,i);
        return result;
    }

    public static int gcd(int a,int b)
    {
        return a>b? recursiveGcd(a,b):recursiveGcd(b,a);
    }

    private static int recursiveGcd(int a,int b)
    {
        int c = a%b;
        if (c == 0)
            return b;
        return recursiveGcd(b,c);
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ @200_success: That's why I used the word "alternative". If it's an alternative solution, then there is not much point in reviewing the original one proposed in the question. In any case, I've expanded my answer in order to elaborate more on the alternative solution suggested. Thank you. \$\endgroup\$ Jan 9 '15 at 8:13
  • 1
    \$\begingroup\$ Alternative solutions are welcome, but this being Code Review, answers need to explain how or why, so that the author can learn how to improve. Your added explanation does make it a better answer. Thank you. \$\endgroup\$ Jan 9 '15 at 8:20
0
\$\begingroup\$

This problem can be solved, with the help of a pocket calculator, simply by thinking a bit about it. The LCM of two numbers is the union of their prime factorizations, i.e., the prime numbers that, when multiplied, result in that number. So LCM(15, 10) = LCM(3 * 5, 2 * 5) = 2 * 3 * 5. All we need to do is find the largest power of each prime found in the prime factorizations of the numbers 1-20, and multiply each of these powers together.

Largest power of 2: 2^3 = 8

Largest power of 3: 3^2 = 9

... the rest of the primes only go up to power 1.

When we multiply these powers together, we get the result you listed: 232792560

\$\endgroup\$
4
  • \$\begingroup\$ How would you implement this into Code? \$\endgroup\$
    – Malachi
    Jan 8 '15 at 20:31
  • \$\begingroup\$ You could type the arithmetic, which is a simple product: 2 * 2 * 2 * 3 * 3 * 5 * ... or you could just type the answer after computing it yourself. \$\endgroup\$
    – meisel
    Jan 8 '15 at 20:40
  • \$\begingroup\$ how would you do this programatically? \$\endgroup\$
    – Malachi
    Jan 8 '15 at 21:52
  • \$\begingroup\$ printf("%lld", 2 * 2 * 2 *...) \$\endgroup\$
    – meisel
    Jan 8 '15 at 22:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.