4
\$\begingroup\$

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:

  1. Is is as efficient as it can be? If not, how can I improve it?
  2. Does it smell?
\$\endgroup\$

4 Answers 4

Reset to default
7
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ The iterative implementation taking considerably less time is not surprising. Recursion introduces a lot of overhead for tiny little functions. \$\endgroup\$ Commented Jan 22, 2015 at 7:00
6
\$\begingroup\$

Optimization 1

You can use the fact that:

 smallestMultiple(a, b) = a * b / gcd(a, b)

and you can calculate gcd (greatest common divisor) efficiently via Euclid's algorithm.

Optimization 2

Apart from that, if you mean by "efficient" that the human should do the maximum possible preprocessing that doesn't involve huge calculations, you can find the lcm(1, ..., 20) quickly by knowing the maximum occurring prime powers:

  • The maximum power of 2 which is ≤ 20: 16
  • The maximum power of 3 which is ≤ 20: 9
  • The maximum power of 5 which is ≤ 20: 5
  • The maximum power of 7 which is ≤ 20: 7
  • ...
  • The maximum power of 19 which is ≤ 20: 19

So the lcm can be calculated most efficiently via:

System.out.println(16*9*5*7*11*13*17*19);

Note that this "optimization" assumes that a human being already knows the primes below 20 and doesn't need to actually calculate them. ;-)

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I like the trick, but don't like the idea of that as an "optimization" you might as well just System.out.println(232792560); \$\endgroup\$ Commented Jan 22, 2015 at 0:00
  • \$\begingroup\$ Yeah, I think "System.out.println(16*9*5*7*11*13*17*19);" is going too far, however writing code to find a) all primes below 20, b) their maximum power less than 20, and c) multiply them together, has a shot at being rather fast. The bottleneck will likely be prime discovery, but a fair optimisation is to pre-calculate the first 100 or so primes which would make this very quick indeed. \$\endgroup\$ Commented Jan 22, 2015 at 17:29
  • \$\begingroup\$ @Danikov: Simply use the sieve of Eratosthenes. It is really fast. You may be concerned about the memory requirement, but since the results become huge quickly, you can't put in large numbers anyway. \$\endgroup\$ Commented Jan 22, 2015 at 19:03
3
\$\begingroup\$

In the main loop, instead of starting from 1, it would be better to start from result + 1. You could also cheat a little. Since the numbers from 11 to 20 include all the maximum prime powers of the numbers from 1 to 10, you can actually set result = 11 instead of 1.

Although with the target range 1-20 in the question an int is big enough, be careful that going further might lead to integer overflow in the result variable. To protect against that you might want to use a long instead.

A note on coding style, the variable names i and j are most commonly used in loops, but in your smallestMultiple they are method parameters, which can be a bit confusing to read.

In my tests, replacing your smallestMultiple method with the lcm method mentioned by @Legato seems to be slightly faster. Since he deleted his answer, I pasted it here (thanks Legato!):

/*Greatest Common Divisor
Euclidean algorithm: http://en.wikipedia.org/wiki/Euclidean_algorithm */
public static long gcd(long a, long b) {
    return b == 0 ? a : gcd(b, a % b); 
}
// Least Common Multiple
public static long lcm(long a, long b) {
    return (a * b) / gcd(a, b);
}
\$\endgroup\$
0
\$\begingroup\$

I would also suggest that you might be able to make use of Java 8 streams to improve your performance on large numbers.

\$\endgroup\$
2
  • \$\begingroup\$ Could you explain why using streams would improve performance? I suspect that the cost of just instantiating a stream would dwarf all calculation time, for such a small problem. \$\endgroup\$ Commented Jan 22, 2015 at 7:56
  • \$\begingroup\$ It's true. I deleted my answer partly because streams start slow. \$\endgroup\$ Commented Jan 22, 2015 at 12:44

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.