Número de divisores
Definir la función
|
1 |
numeroDivisores :: Integer -> Integer |
tal que (numeroDivisores x) es el número de divisores de x. Por ejemplo,
|
1 2 3 |
numeroDivisores 12 == 6 numeroDivisores 25 == 3 length (show (numeroDivisores (product [1..3*10^4]))) == 1948 |
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 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 |
import Data.List (genericLength, group, inits) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck -- 1ª solución -- =========== numeroDivisores1 :: Integer -> Integer numeroDivisores1 x = genericLength [y | y <- [1..x], x `mod` y == 0] -- 2ª solución -- =========== numeroDivisores2 :: Integer -> Integer numeroDivisores2 1 = 1 numeroDivisores2 x | esCuadrado x = 2 * genericLength [y | y <- [1..raizEntera x], x `mod` y == 0] - 1 | otherwise = 2 * genericLength [y | y <- [1..raizEntera x], x `mod` y == 0] -- (raizEntera x) es el mayor número entero cuyo cuadrado es menor o -- igual que x. Por ejemplo, -- raizEntera 3 == 1 -- raizEntera 4 == 2 -- raizEntera 5 == 2 -- raizEntera 8 == 2 -- raizEntera 9 == 3 raizEntera :: Integer -> Integer raizEntera x = floor (sqrt (fromInteger x)) -- (esCuadrado x) se verifica si x es un cuadrado perfecto. Por ejemplo, -- esCuadrado 9 == True -- esCuadrado 7 == False esCuadrado :: Integer -> Bool esCuadrado x = x == (raizEntera x)^2 -- 3ª solución -- =========== numeroDivisores3 :: Integer -> Integer numeroDivisores3 = genericLength . divisores -- (divisores x) es la lista de los divisores de x. Por ejemplo, -- divisores 12 == [1,3,2,6,4,12] -- divisores 25 == [1,5,25] divisores :: Integer -> [Integer] divisores = 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] -- 4ª solución -- =========== numeroDivisores4 :: Integer -> Integer numeroDivisores4 = genericLength . map (product . concat) . sequence . map inits . group . primeFactors -- 5ª solución -- =========== numeroDivisores5 :: Integer -> Integer numeroDivisores5 = product . map ((+1) . genericLength) . group . primeFactors -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_numeroDivisores :: Positive Integer -> Bool prop_numeroDivisores (Positive x) = all (== numeroDivisores1 x) [ numeroDivisores2 x , numeroDivisores3 x , numeroDivisores4 x , numeroDivisores5 x] -- La comprobación es -- λ> quickCheck prop_numeroDivisores -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> numeroDivisores1 (product [1..10]) -- 270 -- (1.67 secs, 726,327,208 bytes) -- λ> numeroDivisores2 (product [1..10]) -- 270 -- (0.01 secs, 929,000 bytes) -- -- λ> numeroDivisores2 (product [1..16]) -- 5376 -- (2.10 secs, 915,864,664 bytes) -- λ> numeroDivisores3 (product [1..16]) -- 5376 -- (0.01 secs, 548,472 bytes) -- -- λ> numeroDivisores3 (product [1..30]) -- 2332800 -- (3.80 secs, 4,149,811,688 bytes) -- λ> numeroDivisores4 (product [1..30]) -- 2332800 -- (0.59 secs, 722,253,848 bytes) -- λ> numeroDivisores5 (product [1..30]) -- 2332800 -- (0.00 secs, 587,856 bytes) |
El código se encuentra en GitHub.