My first approach was not successful:

Even though it could compute the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder, it didn't work for 1 to 20.

It consumed to much memory.

So I used pen and paper to devise a better approach to solve the problem.

I saw that the numbers from 1 to 10 which multiplied produce 2520 are 9, 8, 7 and 5.

What these numbers have in common is that they all have one prime factor with the highest possible multiplicity in the 1 to 10 range.

This is the code that I derived from those two facts:

which yields the right result.

**Update:**

As Leo pointed out in his comment, the answer is the least common multiple of the numbers from 1 to 20.

This is the final (more elegant and much simpler than the previous one) solution to the problem:

en verdad te están pidiendo el Minimo Comun Multiplo, una forma es calcular el Maximo Comun Divisor con algoritmo de Euclides, y mcm(a,b) * mcd(a,b) = a * b

ReplyDeletehttps://github.com/lantoli/euler/blob/master/005_Smallest%20multiple_LCM.go

Muy chulas tus soluciones en Clojure

Muchas gracias!!

Delete