Project Euler is back with a math problem that’ll take some tuning to be efficient.

## Problem 5:

### Smallest Multiple

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?

My first attempt yielded the correct result, but took 4 minutes to finish! All Project Euler problems should take no longer than 60 seconds to complete, so this won’t be good enough…

DECLARE lower_limit PLS_INTEGER := 1; upper_limit PLS_INTEGER := 20; answer PLS_INTEGER; i PLS_INTEGER := 1; BEGIN WHILE answer IS NULL LOOP FOR x IN lower_limit..upper_limit LOOP IF REMAINDER(i, x) = 0 THEN --number is evenly divisible, do nothing to continue checking null; ELSE --attempt next number i := i + 1; exit; END IF; IF x = upper_limit THEN --final number is divisible which means we found our answer answer := i; dbms_output.put_line(answer); END IF; END LOOP; END LOOP; END; --output: 232792560

The first change I made was to start `i`

at our `upper_limit`

of 20, since our answer must be a whole number we don’t need to waste time checking numbers below our upper range. We can also raise the `lower_limit`

to 2, as every number will be divisible by 1. These changes won’t save us much time, but they’re worth doing.

The next thing I realized is the answer can’t possibly be an odd number as it won’t be divisible by 2, which means we can increment `i`

by 2, only checking even numbers as possible answers. If our `upper_limit`

is an odd number, we need to add some logic to only increment by 1 the first time we loop and then by 2 every time after, so I did that as well. I also added a `REVERSE`

to our range, as we’ll more quickly find a non-answer when we divide by 20 or 19, versus dividing by 2, 3, 4, etc.

All these changes brought the run-time down to 55 seconds, which makes it an acceptable answer!

DECLARE lower_limit PLS_INTEGER := 2; upper_limit PLS_INTEGER := 20; answer PLS_INTEGER; i PLS_INTEGER := upper_limit; is_i_even BOOLEAN; BEGIN --see if our starting point is even or odd IF REMAINDER(i,2) = 0 THEN is_i_even := TRUE; ELSE is_i_even := FALSE; END IF; WHILE answer IS NULL LOOP FOR x IN REVERSE lower_limit..upper_limit LOOP IF REMAINDER(i, x) = 0 THEN --number is evenly divisible IF x = lower_limit THEN answer := i; dbms_output.put_line(answer); END IF; ELSE IF is_i_even THEN i := i + 2; exit; ELSE --we only get here if the number is odd to start with i := i + 1; is_i_even := TRUE; exit; END IF; END IF; END LOOP; END LOOP; END; --output: 232792560

I’m no mathematician, so this is as far as I’ll go.

Questions or comments? Feel free to leave them below or reach out to me on Twitter!

I recommend incrementing your test value by 19*20, as that is the minimum interval where those 2 values will be divisible. This brings my execution time down to 1 second.