Smallest multiple

Fork me on GitHub

Problem 005: 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?

45*00p110p120p >10g20g*10p00g20g1+:20p`#v_10g.@
               ^_v#`g00p03+1:g03   <p031<         v <
                 >10g30g%          |1              <^        p01/g03g01<
                                   >10g30g/40p150p  > 20g50g1+:50p` #v_^
                 ^                                < |!%g05g04        <
Stack:   (0)


We start with a value of 1. Then we multiply one after another the numbers from 1 to 20 to our value (We call these multiplicand in the loop).

After each multiplications we search go through the numbers from 2 to value and search for a number divisor where

  • value % divisor == 0
  • (value / divisor) % {0, multiplicand} == 0

Then (after we found such a number) we can reduce the value with it (value /= divisor).

The reduction steps guarantees us that we find the smallest number and it prevents our Int64 numbers from overflowing

Interpreter steps: 50 166
Execution time (BefunExec): 47ms (1.07 MHz)
Program size: 73 x 6 (fully conform befunge-93)
Solution: 232792560
Solved at: 2014-09-11

made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript