What is the smallest number divisible by each of the numbers 1 to 20?

This question appeared on Project Euler. I thought of giving it a try using PL/SQL. Before I started to code, I thought of simplifying so that I can reach to the solution in most efficient way.

Any number which is divisible 20 is also divisible by 10, 5 and 1. Similarly, any number divisible by 18 is also divisible by 9. Following is the list of numbers:

Number	Divisible by
20	10, 5, 1
18	9, 1
16	8, 4, 2, 1
14	7, 1
12	6, 3, 2, 1
10	5, 1
8	4, 2, 1
6	3, 2, 1
4	2, 1

Any number divisible by 11 through 20 is also divisible by 1 through 10. So, basically we need to find a number which is divisible by all the number starting from 11 to 20.

We can easily write a PL/SQL code for this, but by what number should the loop increment by. Logically, any number which is divisible by each of the numbers 11 to 20 should be a multiple of 20. So, we need to increment by loop by 20.

Now that the problem is simplified, we can start our PL/SQL code.

SQL> set serveroutput on

SQL>

SQL> set timing on

SQL>

SQL> Declare

2 l_Result Boolean := FALSE;

3 l_Incr Number := 20;

4 l_Solution Number := 0;

5 Begin

6 while NOT l_Result loop

7 l_Solution := l_Solution + l_Incr;

8 If Mod(l_Solution, 11) = 0 And

9 Mod(l_Solution, 12) = 0 And

10 Mod(l_Solution, 13) = 0 And

11 Mod(l_Solution, 14) = 0 And

12 Mod(l_Solution, 15) = 0 And

13 Mod(l_Solution, 16) = 0 And

14 Mod(l_Solution, 17) = 0 And

15 Mod(l_Solution, 18) = 0 And

16 Mod(l_Solution, 19) = 0 And

17 Mod(l_Solution, 20) = 0 Then

18 l_Result := TRUE;

19 End If;

20 end loop;

21 Dbms_output.put_line('Iterations : ' || l_Solution/l_Incr);

22 Dbms_output.put_line('Smallest Number is : ' || l_Solution);

23 End;

24 /

Iterations : 11639628

Smallest Number is : 232792560

PL/SQL procedure successfully completed.

Elapsed: 00:00:10.98

SQL>

“232792560” is the smallest number which is divisible by each of the numbers 1 to 20 and to reach to the solution we performed “11639628” iterations.

Please share your views, if you think we can further simply or optimize this problem and reach to an efficient solution.

Happy reading !!!