Conjunto de divisores
Definir la función
1 |
divisores :: Integer -> [Integer] |
tal que (divisores x)
es el conjunto de divisores de x
. Por ejemplo,
1 2 3 |
divisores 30 == [1,2,3,5,6,10,15,30] length (divisores (product [1..10])) == 270 length (divisores (product [1..25])) == 340032 |
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 99 100 101 102 103 104 105 106 107 |
import Data.List (group, inits, nub, sort, subsequences) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck -- 1ª solución -- =========== divisores1 :: Integer -> [Integer] divisores1 n = [x | x <- [1..n], n `rem` x == 0] -- 2ª solución -- =========== divisores2 :: Integer -> [Integer] divisores2 n = filter ((== 0) . mod n) [1..n] -- 3ª solución -- =========== divisores3 :: Integer -> [Integer] divisores3 = nub . sort . map product . subsequences . primeFactors -- 4ª solución -- =========== divisores4 :: Integer -> [Integer] divisores4 = sort . map (product . concat) . productoCartesiano . map inits . group . primeFactors -- (productoCartesiano xss) es el producto cartesiano de los conjuntos -- xss. Por ejemplo, -- λ> productoCartesiano [[1,3],[2,5],[6,4]] -- [[1,2,6],[1,2,4],[1,5,6],[1,5,4],[3,2,6],[3,2,4],[3,5,6],[3,5,4]] productoCartesiano :: [[a]] -> [[a]] productoCartesiano [] = [[]] productoCartesiano (xs:xss) = [x:ys | x <- xs, ys <- productoCartesiano xss] -- 5ª solución -- =========== divisores5 :: Integer -> [Integer] divisores5 = sort . map (product . concat) . sequence . map inits . group . primeFactors -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_divisores :: Positive Integer -> Bool prop_divisores (Positive n) = all (== divisores1 n) [ divisores2 n , divisores3 n , divisores4 n , divisores5 n ] -- La comprobación es -- λ> quickCheck prop_divisores -- +++ OK, passed 100 tests. -- Comparación de la eficiencia -- ============================ -- λ> length (divisores (product [1..11])) -- 540 -- (12.51 secs, 7,983,499,736 bytes) -- λ> length (divisores2 (product [1..11])) -- 540 -- (4.81 secs, 4,790,146,656 bytes) -- λ> length (divisores3 (product [1..11])) -- 540 -- (0.10 secs, 107,339,848 bytes) -- λ> length (divisores4 (product [1..11])) -- 540 -- (0.02 secs, 1,702,616 bytes) -- λ> length (divisores5 (product [1..11])) -- 540 -- (0.02 secs, 1,205,824 bytes) -- -- λ> length (divisores3 (product [1..14])) -- 2592 -- (7.89 secs, 9,378,454,912 bytes) -- λ> length (divisores4 (product [1..14])) -- 2592 -- (0.03 secs, 9,426,528 bytes) -- λ> length (divisores5 (product [1..14])) -- 2592 -- (0.02 secs, 6,636,608 bytes) -- -- λ> length (divisores4 (product [1..25])) -- 340032 -- (1.65 secs, 2,055,558,208 bytes) -- λ> length (divisores5 (product [1..25])) -- 340032 -- (0.88 secs, 1,532,515,304 bytes) |
El código se encuentra en GitHub.