Definir la función
numeroDivisores :: Integer -> Integer |
tal que (numeroDivisores x) es el número de divisores de x. Por ejemplo,
numeroDivisores 12 == 6 numeroDivisores 25 == 3 length (show (numeroDivisores (product [1..3*10^4]))) == 1948 |
Soluciones
import Data.List (genericLength, group, inits) import Data.Numbers.Primes (primeFactors) -- 1ª solución -- =========== numeroDivisores :: Integer -> Integer numeroDivisores = 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] -- 2ª solución -- =========== numeroDivisores2 :: Integer -> Integer numeroDivisores2 = genericLength . map (product . concat) . sequence . map inits . group . primeFactors -- 3ª solución -- =========== numeroDivisores3 :: Integer -> Integer numeroDivisores3 = product . map ((+1) . genericLength) . group . primeFactors -- Comparación de la eficiencia -- ============================ -- λ> numeroDivisores (product [1..30]) -- 2332800 -- (4.19 secs, 4,130,692,448 bytes) -- λ> numeroDivisores2 (product [1..30]) -- 2332800 -- (1.16 secs, 703,167,152 bytes) -- λ> numeroDivisores3 (product [1..30]) -- 2332800 -- (0.01 secs, 165,168 bytes) -- -- λ> numeroDivisores2 (product [1..34]) -- 12165120 -- (6.71 secs, 3,657,624,208 bytes) -- λ> numeroDivisores3 (product [1..34]) -- 12165120 -- (0.01 secs, 173,968 bytes) -- -- λ> numeroDivisores2 (product [1..35]) -- *** Exception: stack overflow -- λ> numeroDivisores3 (product [1..35]) -- 16422912 -- (0.00 secs, 174,024 bytes) |
Pensamiento
“Lo que tenemos que aprender a hacer, lo aprendemos haciéndolo.” ~ Aristóteles
4 soluciones de “Número de divisores”
Los comentarios están cerrados.