Menu Close

Número de divisores

 

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

Medio

4 soluciones de “Número de divisores

  1. JOSÉ CARLOS PÉREZ GARRIDO
    numeroDivisores :: Integer -> Integer
    numeroDivisores x = fromIntegral (length (divisores x))
     
    divisores x = [y | y <- [1..x], rem x y == 0]
  2. claniecas
    import Data.List (group, genericLength)
    import Data.Numbers.Primes
     
    numeroDivisores :: Integer -> Integer
    numeroDivisores n = product [x+1 | x <- exponentes n]
     
    exponentes :: Integer -> [Integer]
    exponentes n = map genericLength (group (primeFactors n))
  3. antgongar
    import Data.List (genericLength, group)
    import Data.Numbers.Primes (primeFactors)
     
    numeroDivisores :: Integer -> Integer
    numeroDivisores =
      product . map ((+1) . genericLength) . group . primeFactors
  4. bercabdel
    import Data.List (genericLength, group, inits)
    import Data.Numbers.Primes (primeFactors)
     
    numeroDivisores :: Integer -> Integer
    numeroDivisores = genericLength
                    . map (product . concat)
                    . sequence
                    . map inits
                    . group
                    . primeFactors

Los comentarios están cerrados.