Factorización prima
La descomposición prima de 600 es
|
1 |
600 = 2³ * 3 * 5² |
Definir la función
|
1 |
factorizacion :: Integer -> [(Integer,Integer)] |
tal que (factorizacion x) ses la lista de las bases y exponentes de la descomposición prima de x. Por ejemplo,
|
1 2 |
factorizacion 600 == [(2,3),(3,1),(5,2)] length (factorizacion (product [1..3*10^4])) == 3245 |
Soluciones
|
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 |
import Data.List (genericLength, group, inits, nub, sort, subsequences) import Data.Numbers.Primes (primes, primeFactors) -- 1ª solución -- =========== factorizacion :: Integer -> [(Integer,Integer)] factorizacion n = [(x,nOcurrencias x xs) | x <- elementos xs] where xs = factoresPrimos n -- (factores primos n) es la lista de los factores primos de n. Por -- ejemplo, -- factoresPrimos 600 == [2,2,2,3,5,5] factoresPrimos :: Integer -> [Integer] factoresPrimos 1 = [] factoresPrimos n = x : factoresPrimos (n `div` x) where x = menorFactor n -- (menorFactor n) es el menor factor primo de n. Por ejemplo, -- menorFactor 10 == 2 -- menorFactor 11 == 11 menorFactor :: Integer -> Integer menorFactor n = head [x | x <- [2..n], n `mod` x == 0] -- (elementos xs) es la lista de los elementos, sin repeticiones, de -- xs. Por ejemplo, -- elementos [3,2,3,5,2] == [3,2,5] elementos :: Eq a => [a] -> [a] elementos [] = [] elementos (x:xs) = x : elementos (filter (/=x) xs) -- (nOcurrencias x ys) es el número de ocurrencias de x en ys. Por -- ejemplo, -- nOcurrencias 'a' "Salamanca" == 4 nOcurrencias :: Eq a => a -> [a] -> Integer nOcurrencias x ys = genericLength (filter (==x) ys) -- 2ª solución -- =========== factorizacion2 :: Integer -> [(Integer,Integer)] factorizacion2 n = [(head xs,genericLength xs) | xs <- group (primeFactors n)] -- 3ª solución -- =========== factorizacion3 :: Integer -> [(Integer,Integer)] factorizacion3 = map primeroYlongitud . group . primeFactors -- (primeroYlongitud xs) es el par formado por el primer elemento de xs -- y la longitud de xs. Por ejemplo, -- primeroYlongitud [3,2,5,7] == (3,4) primeroYlongitud :: [a] -> (a,Integer) primeroYlongitud (x:xs) = (x, 1 + genericLength xs) -- Comparación de eficiencia de sumaDivisores -- ========================================== -- λ> length (factorizacion (product [1..10^4])) -- 1229 -- (4.84 secs, 2,583,331,768 bytes) -- λ> length (factorizacion2 (product [1..10^4])) -- 1229 -- (0.24 secs, 452,543,360 bytes) -- λ> length (factorizacion3 (product [1..10^4])) -- 1229 -- (0.23 secs, 452,433,504 bytes) -- -- λ> length (factorizacion (product (take (2*10^3) primes))) -- 2000 -- (6.58 secs, 3,415,098,552 bytes) -- λ> length (factorizacion2 (product (take (2*10^3) primes))) -- 2000 -- (0.02 secs, 23,060,512 bytes) -- λ> length (factorizacion3 (product (take (2*10^3) primes))) -- 2000 -- (0.02 secs, 22,882,080 bytes) |
Pensamiento
¿Todo para los demás?
Mancebo, llena tu jarro,
que ya te lo beberán.Antonio Machado