# Project Euler in PL/SQL: Problem 5

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;
i PLS_INTEGER := 1;
BEGIN
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
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;
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;

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
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!

## 1 thought on “Project Euler in PL/SQL: Problem 5”

1. 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.