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