Menu Close

Número de divisores compuestos

José A. Alonso,

Definir la función

   nDivisoresCompuestos :: Integer -> Integer

tal que (nDivisoresCompuestos x) es el número de divisores de x que son compuestos (es decir, números mayores que 1 que no son primos). Por ejemplo, 

   nDivisoresCompuestos 30  ==  4
   nDivisoresCompuestos (product [1..11])  ==  534
   nDivisoresCompuestos (product [1..25])  ==  340022
   length (show (nDivisoresCompuestos (product [1..3*10^4]))) == 1948

Soluciones

import Data.List (genericLength, group, inits, sort)
import Data.Numbers.Primes (primeFactors)
import Test.QuickCheck
 
-- 1ª solución
-- ===========
 
--    nDivisoresCompuestos 30  ==  4
nDivisoresCompuestos :: Integer -> Integer
nDivisoresCompuestos =
  genericLength . divisoresCompuestos
 
-- (divisoresCompuestos x) es la lista de los divisores de x que
-- son números compuestos (es decir, números mayores que 1 que no son
-- primos). Por ejemplo,
--    divisoresCompuestos 30  ==  [6,10,15,30]
divisoresCompuestos :: Integer -> [Integer]
divisoresCompuestos =
  sort
  . map product
  . compuestos
  . map concat
  . productoCartesiano
  . map inits
  . group
  . primeFactors
  where compuestos xss = [xs | xs <- xss, length xs > 1]  
 
-- (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
-- ===========
 
nDivisoresCompuestos2 :: Integer -> Integer
nDivisoresCompuestos2 x =
  nDivisores x - nDivisoresPrimos x - 1
 
-- (nDivisores x) es el número de divisores de x. Por ejemplo, 
--    nDivisores 30  ==  8
nDivisores :: Integer -> Integer
nDivisores x =
  product [1 + genericLength xs | xs <- group (primeFactors x)]
 
-- (nDivisoresPrimos x) es el número de divisores primos de x. Por
-- ejemplo,  
--    nDivisoresPrimos 30  ==  3
nDivisoresPrimos :: Integer -> Integer
nDivisoresPrimos =
  genericLength . group . primeFactors 
 
-- 3ª solución
-- ===========
 
nDivisoresCompuestos3 :: Integer -> Integer
nDivisoresCompuestos3 x =
  nDivisores - nDivisoresPrimos - 1
  where xss              = group (primeFactors x)
        nDivisores       = product [1 + genericLength xs | xs <-xss]
        nDivisoresPrimos = genericLength xss
 
-- Equivalencia de las definiciones
-- ================================
 
-- La propiedad es
prop_nDivisoresCompuestos :: (Positive Integer) -> Bool
prop_nDivisoresCompuestos (Positive x) =
  all (== nDivisoresCompuestos x) [f x | f <- [ nDivisoresCompuestos2
                                              , nDivisoresCompuestos3 ]]
 
-- La comprobación es
--    λ> quickCheck prop_nDivisoresCompuestos
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
--    λ> nDivisoresCompuestos (product [1..25])
--    340022
--    (2.04 secs, 2,232,146,776 bytes)
--    λ> nDivisoresCompuestos2 (product [1..25])
--    340022
--    (0.00 secs, 220,192 bytes)
--    
--    λ> length (show (nDivisoresCompuestos2 (product [1..3*10^4])))
--    1948
--    (5.22 secs, 8,431,630,288 bytes)
--    λ> length (show (nDivisoresCompuestos3 (product [1..3*10^4])))
--    1948
--    (3.06 secs, 4,662,277,664 bytes)

Pensamiento

“Lo corriente en el hombre es la tendencia a creer verdadero cuanto le
reporta alguna utilidad. Por eso hay tantos hombres capaces de comulgar
con ruedas de molino.”

Antonio Machado

Medio
, , , , , , , , , , ,

6 soluciones de “Número de divisores compuestos”

  1. Responder
    frahidzam

    Una primera solución usando la de ayer

    import Data.List (nub, group, genericLength)
import Data.Numbers.Primes (primeFactors)
 
nDivisoresCompuestos' :: Integer -> Integer
nDivisoresCompuestos' n =
  nDivisores n - genericLength (nub (primeFactors n)) - 1
 
nDivisores :: Integer -> Integer
nDivisores n =
  product [b+1 | b <- map genericLength (group (primeFactors n))]

    Una segunda solución más eficiente

    import Data.List (nub, group, genericLength)
import Data.Numbers.Primes (primeFactors)
 
nDivisoresCompuestos' :: Integer -> Integer
nDivisoresCompuestos' n =
  nDivisores n - genericLength (nub (primeFactors n)) - 1
 
nDivisores :: Integer -> Integer
nDivisores n =
  product [b+1 | b <- map genericLength (group (primeFactors n))]
  2. Responder
    adogargon 
    import Data.Numbers.Primes (primeFactors)
import Data.List (genericLength)
 
nDivisoresCompuestos :: Integer -> Integer
nDivisoresCompuestos n =
  genericLength (factores n) - genericLength (nub (primeFactors n))
 
factores :: Integer -> [Integer]
factores x = [n | n <- [2..x] , x `mod` n == 0]
  3. Responder
    sermurgar 
    import Data.List (genericLength)
 
nDivisoresCompuestos :: Integer -> Integer
nDivisoresCompuestos = genericLength . divisoresCompuestos
 
divisoresCompuestos :: Integer -> [Integer]
divisoresCompuestos x = [m | m <-factores2 x, (not . esPrimo) m ]
 
factores2 :: Integer -> [Integer]
factores2 x = [m | m <- [2..x], mod x m == 0]
 
esPrimo :: Integer -> Bool
esPrimo x = [m | m <- [1..x], mod x m == 0] == [1,x]
  4. Responder
    luipromor 
    nDivisoresCompuestos :: Integer -> Integer
nDivisoresCompuestos = genericLength . divisoresCompuestos
 
divisoresCompuestos :: Integer -> [Integer]
divisoresCompuestos x =
  [n | n <- [4..x], mod x n == 0 && (not . isPrime) n]
  5. Responder
    javmarcha1 
    import Data.Numbers.Primes (primeFactors)
import Data.List (nub, subsequences)
 
nDivisoresCompuestos :: Integer -> Integer
nDivisoresCompuestos x =
  genericLength (tail [y | y <- nub [ product xs
                                    | xs <- subsequences (primeFactors x)]
                         , isPrime y == False])
  6. Responder
    ireprirod 
    import Data.Numbers.Primes (primeFactors)
import Data.List (genericLength, group, nub)
 
nDivisoresCompuestos :: Integer -> Integer
nDivisoresCompuestos n = nDivisores n - nDivisoresSimples n
 
nDivisores :: Integer-> Integer
nDivisores n = product (map (+1) (exponentesFactorizacion n))
 
exponentesFactorizacion :: Integer -> [Integer]
exponentesFactorizacion n = map genericLength (group (primeFactors n))
 
nDivisoresSimples :: Integer -> Integer
nDivisoresSimples n = 1 + genericLength (nub (primeFactors n))

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.