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
1. Soluciones en Haskell
import Data.List (genericLength, group, inits) import Data.Numbers.Primes (primeFactors) import Test.Hspec (Spec, describe, hspec, it, shouldBe) 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 -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: (Integer -> Integer) -> Spec specG numeroDivisores = do it "e1" $ numeroDivisores 12 `shouldBe` 6 it "e2" $ numeroDivisores 25 `shouldBe` 3 spec :: Spec spec = do describe "def. 1" $ specG numeroDivisores1 describe "def. 2" $ specG numeroDivisores2 describe "def. 3" $ specG numeroDivisores3 describe "def. 4" $ specG numeroDivisores4 describe "def. 5" $ specG numeroDivisores5 -- La verificación es -- λ> verifica -- 10 examples, 0 failures -- 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)
2. Soluciones en Python
from itertools import combinations, groupby from itertools import product as cartesian_product from math import prod from timeit import Timer, default_timer from hypothesis import given from hypothesis import strategies as st from sympy import divisor_count, divisors, factorint # 1ª solución # =========== def numeroDivisores1(x: int) -> int: return len([y for y in range(1, x+1) if x % y == 0]) # 2ª solución # =========== # 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 def raizEntera(x: int) -> int: def aux(a: int, b: int) -> int: c = (a+b) // 2 d = c**2 if d == x: return c if c == a: return c if x <= d: return aux(a,c) return aux(c,b) return aux(1,x) # esCuadrado(x) se verifica si x es un cuadrado perfecto. Por ejemplo, # esCuadrado(9) == True # esCuadrado(7) == False def esCuadrado (x: int) -> bool: return x == raizEntera(x) ** 2 def numeroDivisores2(x: int) -> int: if x == 1: return 1 if esCuadrado(x): return 2 * len([y for y in range(1, 1+raizEntera(x)) if x % y == 0]) - 1 return 2 * len([y for y in range(1, 1+raizEntera(x)) if x % y == 0]) # 3ª solución # =========== # primeFactors(n) es la lista de los factores primos de n. Por ejemplo, # >>> primeFactors(12) # [2, 2, 3] def primeFactors(n: int) -> list[int]: return [a for a, b in factorint(n).items() for _ in range(b)] # subsequences(xs) es la lista de las subsecuencias de xs; es decir, de # las listas obtenidas eliminando algunos elementos de xs sin cambiar el # orden de los elementos restantes. Por ejemplo, # >>> subsequences([1,2,3]) # [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] def subsequences(xs: list[int]) -> list[list[int]]: return [list(ys) for i in range(len(xs) + 1) for ys in combinations(xs, i)] # divisores3(n) es el conjunto de los divisores de n. Por ejemplo, # divisores3(30) == [1,2,3,5,6,10,15,30] def divisores3(n: int) -> list[int]: return sorted(set(map(prod, subsequences(primeFactors(n))))) def numeroDivisores3(n: int) -> int: return len(divisores3(n)) # 4ª solución # =========== # inits(xs) es la lista de los segmentos iniciales de xs. Por ejemplo, # >>> inits([3,2,5,2]) # [[], [3], [3, 2], [3, 2, 5], [3, 2, 5, 2]] def inits(xs: list[int]) -> list[list[int]]: return [xs[:i] for i in range(len(xs) + 1)] # productoCartesiano(xss) es el producto cartesiano de los conjuntos # xss. Por ejemplo, # >>> productoCartesiano([[[2, 2]], [[], [3]], [[], [5]]]) # [[[2,2],[],[]],[[2,2],[],[5]],[[2,2],[3],[]],[[2,2],[3],[5]]] def productoCartesiano(xss: list[list[list[int]]]) -> list[list[list[int]]]: return [list(t) for t in cartesian_product(*xss)] # concat(xss) es la lista obtenida concatenando los elementos de # xss. Por ejemplo, # >>> concat([[2], [1,3], [5,2]]) # [2, 1, 3, 5, 2] def concat(xss: list[list[int]]) -> list[int]: return sum(xss, []) # divisores4(n) es el conjunto de los divisores de n. Por ejemplo, # divisores4(30) == [1,2,3,5,6,10,15,30] def divisores4(n: int) -> list[int]: factores = primeFactors(n) factoresAgrupados = [list(g) for k, g in groupby(factores)] return sorted({prod(concat(xss)) for xss in productoCartesiano(list(map(inits, factoresAgrupados)))}) def numeroDivisores4(n: int) -> int: return len(divisores4(n)) # 5ª solución # =========== def numeroDivisores5(n: int) -> int: factores = primeFactors(n) factoresAgrupados = [list(g) for k, g in groupby(factores)] return prod([1 + len(xs) for xs in factoresAgrupados]) # 6ª solución # =========== def numeroDivisores6(n: int) -> int: return len(divisors(n)) # 7ª solución # =========== def numeroDivisores7(n: int) -> int: return divisor_count(n) # Verificación # ============ def test_numeroDivisores() -> None: for numeroDivisores in [numeroDivisores1, numeroDivisores2, numeroDivisores3, numeroDivisores4, numeroDivisores5, numeroDivisores6, numeroDivisores7]: assert numeroDivisores(12) == 6 assert numeroDivisores(25) == 3 print("Verificado") # La verificación es # >>> test_numeroDivisores() # Verificado # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=1, max_value=1000)) def test_numeroDivisores_equiv(x: int) -> None: r = numeroDivisores1(x) assert numeroDivisores2(x) == r assert numeroDivisores3(x) == r assert numeroDivisores4(x) == r assert numeroDivisores5(x) == r assert numeroDivisores6(x) == r assert numeroDivisores7(x) == r # La comprobación es # >>> test_numeroDivisores_equiv() # >>> # Comparación de eficiencia # ========================= def tiempo(e: str) -> None: """Tiempo (en segundos) de evaluar la expresión e.""" t = Timer(e, "", default_timer, globals()).timeit(1) print(f"{t:0.2f} segundos") # La comparación es # >>> tiempo('numeroDivisores1(prod(range(1, 12)))') # 2.02 segundos # >>> tiempo('numeroDivisores2(prod(range(1, 12)))') # 0.00 segundos # >>> tiempo('numeroDivisores3(prod(range(1, 12)))') # 0.06 segundos # # >>> tiempo('numeroDivisores2(prod(range(1, 15)))') # 0.06 segundos # >>> tiempo('numeroDivisores3(prod(range(1, 15)))') # 1.52 segundos # # >>> tiempo('numeroDivisores2(prod(range(1, 18)))') # 1.56 segundos # >>> tiempo('numeroDivisores4(prod(range(1, 18)))') # 0.04 segundos # # >>> tiempo('numeroDivisores4(prod(range(1, 30)))') # 4.29 segundos # >>> tiempo('numeroDivisores5(prod(range(1, 30)))') # 0.00 segundos # >>> tiempo('numeroDivisores6(prod(range(1, 30)))') # 0.96 segundos # >>> tiempo('numeroDivisores7(prod(range(1, 30)))') # 0.00 segundos # # >>> tiempo('numeroDivisores5(prod(range(1, 32)))') # 0.00 segundos # >>> tiempo('numeroDivisores6(prod(range(1, 32)))') # 2.79 segundos # >>> tiempo('numeroDivisores7(prod(range(1, 32)))') # 0.00 segundos # # >>> tiempo('numeroDivisores5(prod(range(1, 4*10**4)))') # 4.91 segundos # >>> tiempo('numeroDivisores7(prod(range(1, 4*10**4)))') # 4.88 segundos