Parejas de números y divisores
Definir la función
1 |
divisoresHasta :: Int -> [(Int,Int)] |
tal que (divisoresHasta n)
es la lista de los pares (a,b)
tales que a
es un número entre 2 y n
y b
es un divisor propio de a
. Por ejemplo,
1 2 3 4 5 6 |
λ> divisoresHasta 6 [(2,1),(3,1),(4,1),(5,1),(6,1),(4,2),(6,2),(6,3)] λ> divisoresHasta 8 [(2,1),(3,1),(4,1),(5,1),(6,1),(7,1),(8,1),(4,2),(6,2),(8,2),(6,3),(8,4)] λ> length (divisoresHasta 1234567) 16272448 |
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 |
import Data.List (sort, sortBy) import Data.Ord (comparing) import Data.Tuple (swap) import Test.QuickCheck -- 1ª solución -- =========== divisoresHasta1 :: Int -> [(Int,Int)] divisoresHasta1 n = ordena (concat [[(a,b) | b <- divisoresPropios a] | a <- [2..n]]) where ordena ps = [intercambia p | p <- sort (map intercambia ps)] intercambia (x,y) = (y,x) divisoresPropios :: Int -> [Int] divisoresPropios n = [x | x <- [1..n `div` 2], n `mod` x == 0] -- 2ª solución -- =========== divisoresHasta2 :: Int -> [(Int,Int)] divisoresHasta2 n = ordena (concat [[(a,b) | b <- divisoresPropios a] | a <- [2..n]]) where ordena = sortBy comp comp (x,y) (u,v) = compare (y,x) (v,u) -- 3ª solución -- =========== divisoresHasta3 :: Int -> [(Int,Int)] divisoresHasta3 n = ordena (concat [[(a,b) | b <- divisoresPropios a] | a <- [2..n]]) where ordena = sortBy (comparing swap) -- 4ª solución -- =========== divisoresHasta4 :: Int -> [(Int,Int)] divisoresHasta4 n = [(a,b) | b <- [1..n `div` 2], a <- [2*b, 3*b..n]] -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_divisoresHasta :: Positive Int -> Bool prop_divisoresHasta (Positive n) = all (== divisoresHasta1 n) [ divisoresHasta2 n , divisoresHasta3 n , divisoresHasta4 n ] -- La comprobación es -- λ> quickCheck prop_divisoresHasta -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (divisoresHasta1 4000) -- 29805 -- (1.78 secs, 843,584,472 bytes) -- λ> length (divisoresHasta2 4000) -- 29805 -- (1.78 secs, 879,421,056 bytes) -- λ> length (divisoresHasta3 4000) -- 29805 -- (1.70 secs, 876,475,584 bytes) -- λ> length (divisoresHasta4 4000) -- 29805 -- (0.02 secs, 6,332,016 bytes) |
El código se encuentra en GitHub.