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?

This time the problem is quite familiar, we need to get factors of a number or rather set of numbers once again, the only difference is the purpose. For the number to be divisible by another it needs to be divisible by all of its prime factors but that's not all. Let's take for example `16`

and `40`

, while `40`

is apparently divisibe by `2`

, it's not enough, it would actually need to be divisible by the greatest power of two in `16`

.

Well, looks like we need to collect all the prime factors and count their greatest powers at the same time. There are many ways to do that, let's keep it simple and declare a bitarray and an array, the first one to hold the prime factors already found, the second one to hold the powers (it'd be a small array anyway, in the range `1..20`

the last prime is `19`

). If we would care for bigger numbers, we could just as well use one array of simple two-value `structs`

and `bsearch`

(even though it'd faster to use `Point2`

values instead of `structs`

for smaller values, `Point2`

uses float value type and that could be a problem for really big values). It could be just as well done with one array only checking for `!= undefined`

but I prefer an additional `bitarray`

for the simplicity of iterating over it.

It makes sense to prepare a little function for setting the values. This one needs to take care of setting new indices and raising powers of existing ones if we suplly it with one. In short, when the index is already defined, we check for its power and if the supplied one is higher we use that one instead. If the index haven't been set yet, we set the index and the supplied power.`local factors = #{}`

`local powers = #()`

Now, for every number in the range we need to find its prime factors and their powers. This time we need to know how many times we've divided the number so instead of recursion I made use of a while loop, the first one checking for multiples of 2 and counting how many times we can divide the number so that it would still be even, the second one dealing with the rest. At the end of the function if the number couldn't be divided any further and it's still bigger than one, we know it's a prime so we set its first power.`fn setPows nr pow =`

`(`

`if factors[nr] then`

`if powers[nr] < pow do`

`powers[nr] = pow`

`else`

`(`

`factors[nr] = true`

`powers[nr] = pow`

`)`

`)`

The only thing that remains is to set the primes and their powers for all the numbers in range. Let's wrap it up in a function called`fn primeFactorsPow nr =`

`(`

`if isEven nr do`

`(`

`local pow = 0L`

`do (nr /= 2L; pow += 1) while isEven nr`

`setPows 2L pow`

`)`

`local rootNr = nr^0.5`

`for i = 3L to rootNr by 2L`

`where mod nr i == 0 do`

`(`

`local pow = 0L`

`do (nr /= i; pow += 1) while mod nr i == 0`

`setPows i pow`

`)`

`if nr > 1 do`

`setPows nr 1L`

`)`

`lowestCommonMultiple`

where we will iterate over the range calling `primeFactorsPow`

for each number and then for all the collected primes multiply the `result`

by the prime to its highest power recorded. For the sake of completeness I include both the functions explained prior as well as the `isEven`

function we've been using almost from the beginning.
`(`

`fn isEven nr = bit.and 1L nr == 0`

`local factors = #{}`

`local powers = #()`

`fn setPows nr pow =`

`(`

`if factors[nr] then`

`if powers[nr] < pow do`

`powers[nr] = pow`

`else`

`(`

`factors[nr] = true`

`powers[nr] = pow`

`)`

`)`

`fn primeFactorsPow nr =`

`(`

`if isEven nr do`

`(`

`local pow = 0L`

`do (nr /= 2L; pow += 1) while isEven nr`

`setPows 2L pow`

`)`

`local rootNr = nr^0.5`

`for i = 3L to rootNr by 2L`

`where mod nr i == 0 do`

`(`

`local pow = 0L`

`do (nr /= i; pow += 1) while mod nr i == 0`

`setPows i pow`

`)`

`if nr > 1 do`

`setPows nr 1L`

`)`

`fn lowestCommonMultiple nrs =`

`(`

`local result = 1L`

`for nr in nrs do`

`primeFactorsPow nr`

`for fact in factors do`

`result *= fact^powers[fact]`

`result`

`)`

`lowestCommonMultiple #{2..20}`

`)`

That's it, not much different from our last encounter with prime factors, I agree, but still an interesting task.

DISCLAIMER: All scripts and snippets are provided as is under Creative Commons Zero (public domain, no restrictions) license. The author and this blog cannot be held liable for any loss caused as a result of inaccuracy or error within these web pages. Use at your own risk.

## This Post needs Your Comment!

Leave a Comment