Definir la funci\u00f3n<\/p>\n
\n divisoresPrimos :: Integer -> [Integer]\n<\/pre>\ntal que divisoresPrimos x<\/code> es la lista de los divisores primos de x<\/code>. Por ejemplo,<\/p>\n\n divisoresPrimos 40 == [2,5]\n divisoresPrimos 70 == [2,5,7]\n length (divisoresPrimos (product [1..20000])) == 2262\n<\/pre>\nSoluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n<\/a>
\nSoluciones en Haskell<\/b><\/p>\n\nimport Data.List (nub)\nimport Data.Set (toList)\nimport Data.Numbers.Primes (isPrime, primeFactors)\nimport Math.NumberTheory.ArithmeticFunctions (divisors)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\ndivisoresPrimos1 :: Integer -> [Integer]\ndivisoresPrimos1 x = [n | n <- divisores1 x, primo1 n]\n\n-- (divisores n) es la lista de los divisores del n\u00famero n. Por ejemplo,\n-- divisores 25 == [1,5,25]\n-- divisores 30 == [1,2,3,5,6,10,15,30]\ndivisores1 :: Integer -> [Integer]\ndivisores1 n = [x | x <- [1..n], n `mod` x == 0]\n\n-- (primo n) se verifica si n es primo. Por ejemplo,\n-- primo 30 == False\n-- primo 31 == True\nprimo1 :: Integer -> Bool\nprimo1 n = divisores1 n == [1, n]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\ndivisoresPrimos2 :: Integer -> [Integer]\ndivisoresPrimos2 x = [n | n <- divisores2 x, primo2 n]\n\ndivisores2 :: Integer -> [Integer]\ndivisores2 n = xs ++ [n `div` y | y <- ys]\n where xs = primerosDivisores2 n\n (z:zs) = reverse xs\n ys | z^2 == n = zs\n | otherwise = z:zs\n\n-- (primerosDivisores n) es la lista de los divisores del n\u00famero n cuyo\n-- cuadrado es menor o gual que n. Por ejemplo,\n-- primerosDivisores 25 == [1,5]\n-- primerosDivisores 30 == [1,2,3,5]\nprimerosDivisores2 :: Integer -> [Integer]\nprimerosDivisores2 n =\n [x | x <- [1..round (sqrt (fromIntegral n))],\n n `mod` x == 0]\n\nprimo2 :: Integer -> Bool\nprimo2 1 = False\nprimo2 n = primerosDivisores2 n == [1]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\ndivisoresPrimos3 :: Integer -> [Integer]\ndivisoresPrimos3 x = [n | n <- divisores3 x, primo3 n]\n\ndivisores3 :: Integer -> [Integer]\ndivisores3 n = xs ++ [n `div` y | y <- ys]\n where xs = primerosDivisores3 n\n (z:zs) = reverse xs\n ys | z^2 == n = zs\n | otherwise = z:zs\n\nprimerosDivisores3 :: Integer -> [Integer]\nprimerosDivisores3 n =\n filter ((== 0) . mod n) [1..round (sqrt (fromIntegral n))]\n\nprimo3 :: Integer -> Bool\nprimo3 1 = False\nprimo3 n = primerosDivisores3 n == [1]\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\ndivisoresPrimos4 :: Integer -> [Integer]\ndivisoresPrimos4 n\n | even n = 2 : divisoresPrimos4 (reducido n 2)\n | otherwise = aux n [3,5..n]\n where aux 1 _ = []\n aux _ [] = []\n aux m (x:xs) | m `mod` x == 0 = x : aux (reducido m x) xs\n | otherwise = aux m xs\n\n-- (reducido m x) es el resultado de dividir repetidamente m por x,\n-- mientras sea divisible. Por ejemplo,\n-- reducido 36 2 == 9\nreducido :: Integer -> Integer -> Integer\nreducido m x | m `mod` x == 0 = reducido (m `div` x) x\n | otherwise = m\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\ndivisoresPrimos5 :: Integer -> [Integer]\ndivisoresPrimos5 = nub . primeFactors\n\n-- 6\u00aa soluci\u00f3n\n-- ===========\n\ndivisoresPrimos6 :: Integer -> [Integer]\ndivisoresPrimos6 = filter isPrime . toList . divisors\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_divisoresPrimos :: Integer -> Property\nprop_divisoresPrimos n =\n n > 1 ==>\n all (== divisoresPrimos1 n)\n [divisoresPrimos2 n,\n divisoresPrimos3 n,\n divisoresPrimos4 n,\n divisoresPrimos5 n,\n divisoresPrimos6 n]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_divisoresPrimos\n-- +++ OK, passed 100 tests; 108 discarded.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> divisoresPrimos1 (product [1..11])\n-- [2,3,5,7,11]\n-- (18.34 secs, 7,984,382,104 bytes)\n-- \u03bb> divisoresPrimos2 (product [1..11])\n-- [2,3,5,7,11]\n-- (0.02 secs, 2,610,976 bytes)\n-- \u03bb> divisoresPrimos3 (product [1..11])\n-- [2,3,5,7,11]\n-- (0.02 secs, 2,078,288 bytes)\n-- \u03bb> divisoresPrimos4 (product [1..11])\n-- [2,3,5,7,11]\n-- (0.02 secs, 565,992 bytes)\n-- \u03bb> divisoresPrimos5 (product [1..11])\n-- [2,3,5,7,11]\n-- (0.01 secs, 568,000 bytes)\n-- \u03bb> divisoresPrimos6 (product [1..11])\n-- [2,3,5,7,11]\n-- (0.00 secs, 2,343,392 bytes)\n--\n-- \u03bb> divisoresPrimos2 (product [1..16])\n-- [2,3,5,7,11,13]\n-- (2.32 secs, 923,142,480 bytes)\n-- \u03bb> divisoresPrimos3 (product [1..16])\n-- [2,3,5,7,11,13]\n-- (0.80 secs, 556,961,088 bytes)\n-- \u03bb> divisoresPrimos4 (product [1..16])\n-- [2,3,5,7,11,13]\n-- (0.01 secs, 572,368 bytes)\n-- \u03bb> divisoresPrimos5 (product [1..16])\n-- [2,3,5,7,11,13]\n-- (0.01 secs, 31,665,896 bytes)\n-- \u03bb> divisoresPrimos6 (product [1..16])\n-- [2,3,5,7,11,13]\n-- (0.01 secs, 18,580,584 bytes)\n--\n-- \u03bb> length (divisoresPrimos4 (product [1..30]))\n-- 10\n-- (0.01 secs, 579,168 bytes)\n-- \u03bb> length (divisoresPrimos5 (product [1..30]))\n-- 10\n-- (0.01 secs, 594,976 bytes)\n-- \u03bb> length (divisoresPrimos6 (product [1..30]))\n-- 10\n-- (3.38 secs, 8,068,783,408 bytes)\n--\n-- \u03bb> length (divisoresPrimos4 (product [1..20000]))\n-- 2262\n-- (1.20 secs, 1,940,069,976 bytes)\n-- \u03bb> length (divisoresPrimos5 (product [1..20000]))\n-- 2262\n-- (1.12 secs, 1,955,921,736 bytes)\n<\/pre>\nEl c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n