Sunday, August 31, 2014

Euler Project: Problem 5 in Clojure

I solved the fifth problem from Euler project in Clojure.

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:

2 comments:

  1. 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
    https://github.com/lantoli/euler/blob/master/005_Smallest%20multiple_LCM.go

    Muy chulas tus soluciones en Clojure

    ReplyDelete