Menor divisible por todos
Definir la función
|
1 |
menorDivisible :: Integer -> Integer -> Integer |
tal que (menorDivisible a b) es el menor número divisible por todos los números desde a hasta b, ambos inclusive. Por ejemplo,
|
1 2 |
menorDivisible 1 10 == 2520 length (show (menorDivisible 1 (3*10^5))) == 130141 |
Nota: Este ejercicio está basado en el problema 5 del Proyecto Euler
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
import Data.List (foldl') -- 1ª solución -- =========== menorDivisible :: Integer -> Integer -> Integer menorDivisible a b = head [x | x <- [b..] , and [x `mod` y == 0 | y <- [a..b]]] -- 2ª solución -- =========== menorDivisible2 :: Integer -> Integer -> Integer menorDivisible2 a b | a == b = a | otherwise = lcm a (menorDivisible (a+1) b) -- 3ª solución -- ============ menorDivisible3 :: Integer -> Integer -> Integer menorDivisible3 a b = foldl lcm 1 [a..b] -- 4ª solución -- =========== menorDivisible4 :: Integer -> Integer -> Integer menorDivisible4 a b = foldl1 lcm [a..b] -- 5ª solución -- =========== menorDivisible5 :: Integer -> Integer -> Integer menorDivisible5 a b = foldl' lcm 1 [a..b] -- 6ª solución -- =========== menorDivisible6 :: Integer -> Integer -> Integer menorDivisible6 a b = foldr1 lcm [a..b] -- 7ª solución -- =========== menorDivisible7 :: Integer -> Integer -> Integer menorDivisible7 a = foldr1 lcm . enumFromTo a -- Comparación de eficiencia -- ========================= -- λ> menorDivisible 1 17 -- 12252240 -- (18.63 secs, 15,789,475,488 bytes) -- λ> menorDivisible2 1 17 -- 12252240 -- (13.29 secs, 11,868,764,272 bytes) -- λ> menorDivisible3 1 17 -- 12252240 -- (0.00 secs, 114,688 bytes) -- λ> menorDivisible4 1 17 -- 12252240 -- (0.01 secs, 114,752 bytes) -- λ> menorDivisible5 1 17 -- 12252240 -- (0.01 secs, 110,640 bytes) -- λ> menorDivisible6 1 17 -- 12252240 -- (0.01 secs, 114,752 bytes) -- λ> menorDivisible7 1 17 -- 12252240 -- (0.00 secs, 110,912 bytes) -- -- λ> length (show (menorDivisible3 1 (10^5))) -- 43452 -- (1.54 secs, 2,021,887,000 bytes) -- λ> length (show (menorDivisible4 1 (10^5))) -- 43452 -- (1.47 secs, 2,021,886,616 bytes) -- λ> length (show (menorDivisible5 1 (10^5))) -- 43452 -- (0.65 secs, 2,009,595,568 bytes) -- λ> length (show (menorDivisible6 1 (10^5))) -- 43452 -- (0.30 secs, 172,986,840 bytes) -- λ> length (show (menorDivisible7 1 (10^5))) -- 43452 -- (0.30 secs, 172,986,920 bytes) -- -- λ> length (show (menorDivisible5 1 (2*10^5))) -- 86871 -- (2.47 secs, 7,989,147,304 bytes) -- λ> length (show (menorDivisible6 1 (2*10^5))) -- 86871 -- (0.89 secs, 533,876,496 bytes) -- λ> length (show (menorDivisible7 1 (2*10^5))) -- 86871 -- (0.88 secs, 533,875,608 bytes) |
Pensamiento
Será el peor de los malos
bribón que olvide
su vocación de diablo.Antonio Machado