Divisores de un número
Definir la función
|
1 |
divisores :: Integer -> [Integer] |
tal que divisores n es la lista de los divisores de n. Por ejemplo,
|
1 2 3 |
divisores 30 == [1,2,3,5,6,10,15,30] length (divisores (product [1..10])) == 270 length (divisores (product [1..25])) == 340032 |
Soluciones
A continuación se muestran las soluciones en Haskell y las soluciones en Python.
|
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 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 |
import Data.List (group, inits, nub, sort, subsequences) import Data.Numbers.Primes (primeFactors) import Data.Set (toList) import Math.NumberTheory.ArithmeticFunctions (divisors) import Test.QuickCheck -- 1ª solución -- =========== divisores1 :: Integer -> [Integer] divisores1 n = [x | x <- [1..n], n `rem` x == 0] -- 2ª solución -- =========== divisores2 :: Integer -> [Integer] divisores2 n = [x | x <- [1..n], x `esDivisorDe` n] -- (esDivisorDe x n) se verifica si x es un divisor de n. Por ejemplo, -- esDivisorDe 2 6 == True -- esDivisorDe 4 6 == False esDivisorDe :: Integer -> Integer -> Bool esDivisorDe x n = n `rem` x == 0 -- 3ª solución -- =========== divisores3 :: Integer -> [Integer] divisores3 n = filter (`esDivisorDe` n) [1..n] -- 4ª solución -- =========== divisores4 :: Integer -> [Integer] divisores4 = filter <$> flip esDivisorDe <*> enumFromTo 1 -- 5ª solución -- =========== divisores5 :: Integer -> [Integer] divisores5 n = xs ++ [n `div` y | y <- ys] where xs = primerosDivisores1 n (z:zs) = reverse xs ys | z^2 == n = zs | otherwise = z:zs -- (primerosDivisores n) es la lista de los divisores del número n cuyo -- cuadrado es menor o gual que n. Por ejemplo, -- primerosDivisores 25 == [1,5] -- primerosDivisores 30 == [1,2,3,5] primerosDivisores1 :: Integer -> [Integer] primerosDivisores1 n = [x | x <- [1..round (sqrt (fromIntegral n))], x `esDivisorDe` n] -- 6ª solución -- =========== divisores6 :: Integer -> [Integer] divisores6 n = aux [1..n] where aux [] = [] aux (x:xs) | x `esDivisorDe` n = x : aux xs | otherwise = aux xs -- 7ª solución -- =========== divisores7 :: Integer -> [Integer] divisores7 n = xs ++ [n `div` y | y <- ys] where xs = primerosDivisores2 n (z:zs) = reverse xs ys | z^2 == n = zs | otherwise = z:zs primerosDivisores2 :: Integer -> [Integer] primerosDivisores2 n = aux [1..round (sqrt (fromIntegral n))] where aux [] = [] aux (x:xs) | x `esDivisorDe` n = x : aux xs | otherwise = aux xs -- 8ª solución -- =========== divisores8 :: Integer -> [Integer] divisores8 = nub . sort . map product . subsequences . primeFactors -- 9ª solución -- =========== divisores9 :: Integer -> [Integer] divisores9 = sort . 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] -- 10ª solución -- ============ divisores10 :: Integer -> [Integer] divisores10 = sort . map (product . concat) . mapM inits . group . primeFactors -- 11ª solución -- ============ divisores11 :: Integer -> [Integer] divisores11 = toList . divisors -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_divisores :: Positive Integer -> Bool prop_divisores (Positive n) = all (== divisores1 n) [ divisores2 n , divisores3 n , divisores4 n , divisores5 n , divisores6 n , divisores7 n , divisores8 n , divisores9 n , divisores10 n , divisores11 n ] -- La comprobación es -- λ> quickCheck prop_divisores -- +++ OK, passed 100 tests. -- Comparación de la eficiencia -- ============================ -- La comparación es -- λ> length (divisores1 (product [1..11])) -- 540 -- (18.55 secs, 7,983,950,592 bytes) -- λ> length (divisores2 (product [1..11])) -- 540 -- (18.81 secs, 7,983,950,592 bytes) -- λ> length (divisores3 (product [1..11])) -- 540 -- (12.79 secs, 6,067,935,544 bytes) -- λ> length (divisores4 (product [1..11])) -- 540 -- (12.51 secs, 6,067,935,592 bytes) -- λ> length (divisores5 (product [1..11])) -- 540 -- (0.03 secs, 1,890,296 bytes) -- λ> length (divisores6 (product [1..11])) -- 540 -- (21.46 secs, 9,899,961,392 bytes) -- λ> length (divisores7 (product [1..11])) -- 540 -- (0.02 secs, 2,195,800 bytes) -- λ> length (divisores8 (product [1..11])) -- 540 -- (0.09 secs, 107,787,272 bytes) -- λ> length (divisores9 (product [1..11])) -- 540 -- (0.02 secs, 2,150,472 bytes) -- λ> length (divisores10 (product [1..11])) -- 540 -- (0.01 secs, 1,652,120 bytes) -- λ> length (divisores11 (product [1..11])) -- 540 -- (0.01 secs, 796,056 bytes) -- -- λ> length (divisores5 (product [1..17])) -- 10752 -- (10.16 secs, 3,773,953,128 bytes) -- λ> length (divisores7 (product [1..17])) -- 10752 -- (9.83 secs, 4,679,260,712 bytes) -- λ> length (divisores9 (product [1..17])) -- 10752 -- (0.06 secs, 46,953,344 bytes) -- λ> length (divisores10 (product [1..17])) -- 10752 -- (0.02 secs, 33,633,712 bytes) -- λ> length (divisores11 (product [1..17])) -- 10752 -- (0.03 secs, 6,129,584 bytes) -- -- λ> length (divisores10 (product [1..27])) -- 677376 -- (2.14 secs, 3,291,277,736 bytes) -- λ> length (divisores11 (product [1..27])) -- 677376 -- (0.56 secs, 396,042,280 bytes) |
El código se encuentra en GitHub.
|
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 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
from math import factorial, sqrt from timeit import Timer, default_timer from sys import setrecursionlimit from sympy import divisors from hypothesis import given, strategies as st setrecursionlimit(10**6) # 1ª solución # =========== def divisores1(n: int) -> list[int]: return [x for x in range(1, n + 1) if n % x == 0] # 2ª solución # =========== # esDivisorDe(x, n) se verifica si x es un divisor de n. Por ejemplo, # esDivisorDe(2, 6) == True # esDivisorDe(4, 6) == False def esDivisorDe(x: int, n: int) -> bool: return n % x == 0 def divisores2(n: int) -> list[int]: return [x for x in range(1, n + 1) if esDivisorDe(x, n)] # 3ª solución # =========== def divisores3(n: int) -> list[int]: return list(filter(lambda x: esDivisorDe(x, n), range(1, n + 1))) # 4ª solución # =========== # primerosDivisores(n) es la lista de los divisores del número n cuyo # cuadrado es menor o gual que n. Por ejemplo, # primerosDivisores(25) == [1,5] # primerosDivisores(30) == [1,2,3,5] def primerosDivisores(n: int) -> list[int]: return [x for x in range(1, 1 + round(sqrt(n))) if n % x == 0] def divisores4(n: int) -> list[int]: xs = primerosDivisores(n) zs = list(reversed(xs)) if zs[0]**2 == n: return xs + [n // a for a in zs[1:]] return xs + [n // a for a in zs] # 5ª solución # =========== def divisores5(n: int) -> list[int]: def aux(xs: list[int]) -> list[int]: if xs: if esDivisorDe(xs[0], n): return [xs[0]] + aux(xs[1:]) return aux(xs[1:]) return xs return aux(list(range(1, n + 1))) # 6ª solución # ============ def divisores6(n: int) -> list[int]: xs = [] for x in range(1, n+1): if n % x == 0: xs.append(x) return xs # 7ª solución # =========== def divisores7(n: int) -> list[int]: x = 1 xs = [] ys = [] while x * x < n: if n % x == 0: xs.append(x) ys.append(n // x) x = x + 1 if x * x == n: xs.append(x) return xs + list(reversed(ys)) # 8ª solución # ============ def divisores8(n: int) -> list[int]: return divisors(n) # Comprobación de equivalencia # ============================ # La propiedad es @given(st.integers(min_value=2, max_value=1000)) def test_divisores(n): assert divisores1(n) ==\ divisores2(n) ==\ divisores3(n) ==\ divisores4(n) ==\ divisores5(n) ==\ divisores6(n) ==\ divisores7(n) ==\ divisores8(n) # La comprobación es # src> poetry run pytest -q divisores_de_un_numero.py # 1 passed in 0.84s # Comparación de eficiencia # ========================= def tiempo(e): """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('divisores5(4*factorial(7))') # 1.40 segundos # # >>> tiempo('divisores1(factorial(11))') # 1.79 segundos # >>> tiempo('divisores2(factorial(11))') # 3.80 segundos # >>> tiempo('divisores3(factorial(11))') # 5.22 segundos # >>> tiempo('divisores4(factorial(11))') # 0.00 segundos # >>> tiempo('divisores6(factorial(11))') # 3.51 segundos # >>> tiempo('divisores7(factorial(11))') # 0.00 segundos # >>> tiempo('divisores8(factorial(11))') # 0.00 segundos # # >>> tiempo('divisores4(factorial(17))') # 2.23 segundos # >>> tiempo('divisores7(factorial(17))') # 3.22 segundos # >>> tiempo('divisores8(factorial(17))') # 0.00 segundos # # >>> tiempo('divisores8(factorial(27))') # 0.28 segundos |
El código se encuentra en GitHub.