Números libres de cuadrados
Un número entero positivo es libre de cuadrados si no es divisible el cuadrado de ningún entero mayor que 1. Por ejemplo, 70 es libre de cuadrado porque sólo es divisible por 1, 2, 5, 7 y 70; en cambio, 40 no es libre de cuadrados porque es divisible por 2^2.
Definir la función
|
1 |
libreDeCuadrados :: Integer -> Bool |
tal que (libreDeCuadrados x) se verifica si x es libre de cuadrados. Por ejemplo,
|
1 2 3 4 |
libreDeCuadrados 70 == True libreDeCuadrados 40 == False libreDeCuadrados 510510 == True libreDeCuadrados (((10^10)^10)^10) == False |
Otro ejemplo,
|
1 2 |
λ> filter (not . libreDeCuadrados) [1..50] [4,8,9,12,16,18,20,24,25,27,28,32,36,40,44,45,48,49,50] |
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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
import Data.Numbers.Primes (primeFactors, primes) import Data.List (nub) import Test.QuickCheck import Data.List (genericLength) -- Para OS -- 1ª definición: libreDeCuadrados :: Integer -> Bool libreDeCuadrados x = x == product (divisoresPrimos x) -- (divisoresPrimos x) es la lista de los divisores primos de x. Por -- ejemplo, -- divisoresPrimos 40 == [2,5] -- divisoresPrimos 70 == [2,5,7] divisoresPrimos :: Integer -> [Integer] divisoresPrimos x = [n | n <- divisores x, primo n] -- (divisores n) es la lista de los divisores del número n. Por ejemplo, -- divisores 30 == [1,2,3,5,6,10,15,30] divisores :: Integer -> [Integer] divisores n = [x | x <- [1..n], n `mod` x == 0] -- (primo n) se verifica si n es primo. Por ejemplo, -- primo 30 == False -- primo 31 == True primo :: Integer -> Bool primo n = divisores n == [1, n] -- 2ª definición libreDeCuadrados2 :: Integer -> Bool libreDeCuadrados2 n = null [x | x <- [2..n], rem n (x^2) == 0] -- 3ª definición libreDeCuadrados3 :: Integer -> Bool libreDeCuadrados3 n = null [x | x <- [2..floor (sqrt (fromIntegral n))], rem n (x^2) == 0] -- 4ª definición libreDeCuadrados4 :: Integer -> Bool libreDeCuadrados4 n = xs == nub xs where xs = primeFactors n -- 5ª definición libreDeCuadrados5 :: Integer -> Bool libreDeCuadrados5 n = all (\(x,y) -> x /= y) (zip xs (tail xs)) where xs = primeFactors n -- Equivalencia de las definiciones -- ================================ prop_equivalencia :: Integer -> Property prop_equivalencia n = n > 0 ==> all (== libreDeCuadrados n) [f n | f <- [ libreDeCuadrados2 , libreDeCuadrados3 , libreDeCuadrados4 , libreDeCuadrados5 ]] -- La comprobación es -- λ> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- λ> libreDeCuadrados 510510 -- True -- (0.76 secs, 89,522,360 bytes) -- λ> libreDeCuadrados2 510510 -- True -- (1.78 secs, 371,826,320 bytes) -- λ> libreDeCuadrados3 510510 -- True -- (0.01 secs, 0 bytes) -- λ> libreDeCuadrados4 510510 -- True -- (0.00 secs, 152,712 bytes) -- -- λ> filter libreDeCuadrados3 [1..] !! (2*10^4) -- 32906 -- (2.24 secs, 1,812,139,456 bytes) -- λ> filter libreDeCuadrados4 [1..] !! (2*10^4) -- 32906 -- (0.51 secs, 936,216,664 bytes) -- λ> filter libreDeCuadrados5 [1..] !! (2*10^4) -- 32906 -- (0.38 secs, 806,833,952 bytes) -- -- λ> filter libreDeCuadrados4 [1..] !! (10^5) -- 164499 -- (3.28 secs, 7,470,629,888 bytes) -- λ> filter libreDeCuadrados5 [1..] !! (10^5) -- 164499 -- (2.88 secs, 6,390,072,384 bytes) |
Lo único que mejoraría de la definición sería que cuando el programa hace » x
notElemxs «, si realmente x no es un elemento de xs, estás tardando un tiempo lineal, en función de (length xs), en comprobarlo. Esto puedes hacerlo mas eficientemente, en tiempo constante, comprobando simplemente si el primer elemento de xs es igual a x, aprovechando así el dato de que en la lista (primeFactors x) si existen dos elementos iguales entonces son consecutivos.La definición se puede mejorar:
1. La lista (primeFactors x) es calculada dos veces.
2. La función nub realiza un trabajo extra calculando la lista sin elementos repetidos de (primeFactors x), en esta función el tiempo es cuadrático en el numero de elementos de la lista (primeFactors x). Cuando, sabiendo que si hay elementos repetidos en (primeFactors x) son consecutivos, podemos simplemente comparar cada elemento con el siguiente, el tiempo es entonces lineal en el numero de elementos de (primeFactors x).