Un n\u00famero es libre de cuadrados si no es divisible por el cuadrado de ning\u00fan entero mayor que 1. Por ejemplo, 70 es libre de cuadrado porque s\u00f3lo es divisible por 1, 2, 5, 7 y 70; en cambio, 40 no es libre de cuadrados porque es divisible por 2^2.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n libreDeCuadrados :: Integer -> Bool\n<\/pre>\ntal que libreDeCuadrados x<\/code> se verifica si x<\/code> es libre de cuadrados. Por ejemplo,<\/p>\n\n libreDeCuadrados 70 == True\n libreDeCuadrados 40 == False\n libreDeCuadrados (product (take 30000 primes)) == True\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.Numbers.Primes (primeFactors, primes)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nlibreDeCuadrados1 :: Integer -> Bool\nlibreDeCuadrados1 n =\n null [x | x <- [2..n], rem n (x^2) == 0]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nlibreDeCuadrados2 :: Integer -> Bool\nlibreDeCuadrados2 x =\n x == product (divisoresPrimos2 x)\n\n-- (divisoresPrimos x) es la lista de los divisores primos de x. Por\n-- ejemplo,\n-- divisoresPrimos 40 == [2,5]\n-- divisoresPrimos 70 == [2,5,7]\ndivisoresPrimos2 :: Integer -> [Integer]\ndivisoresPrimos2 x = [n | n <- divisores2 x, primo2 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]\ndivisores2 :: Integer -> [Integer]\ndivisores2 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\nprimo2 :: Integer -> Bool\nprimo2 n = divisores2 n == [1, n]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nlibreDeCuadrados3 :: Integer -> Bool\nlibreDeCuadrados3 n\n | even n = n `mod` 4 \/= 0 && libreDeCuadrados3 (n `div` 2)\n | otherwise = aux n [3,5..n]\n where aux 1 _ = True\n aux _ [] = True\n aux m (x:xs)\n | m `mod` x == 0 = m `mod` (x^2) \/= 0 && aux (m `div` x) xs\n | otherwise = aux m xs\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nlibreDeCuadrados4 :: Integer -> Bool\nlibreDeCuadrados4 x =\n x == product (divisoresPrimos4 x)\n\ndivisoresPrimos4 :: Integer -> [Integer]\ndivisoresPrimos4 = nub . primeFactors\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nlibreDeCuadrados5 :: Integer -> Bool\nlibreDeCuadrados5 =\n sinRepetidos . primeFactors\n\n-- (sinRepetidos xs) se verifica si xs no tiene elementos repetidos. Por\n-- ejemplo,\n-- sinRepetidos [3,2,5] == True\n-- sinRepetidos [3,2,5,2] == False\nsinRepetidos :: [Integer] -> Bool\nsinRepetidos xs =\n nub xs == xs\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_libreDeCuadrados :: Integer -> Property\nprop_libreDeCuadrados x =\n x > 1 ==>\n all (== libreDeCuadrados1 x)\n [libreDeCuadrados2 x,\n libreDeCuadrados3 x,\n libreDeCuadrados4 x,\n libreDeCuadrados5 x]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_libreDeCuadrados\n-- +++ OK, passed 100 tests; 165 discarded.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> libreDeCuadrados1 9699690\n-- True\n-- (8.54 secs, 6,441,144,248 bytes)\n-- \u03bb> libreDeCuadrados2 9699690\n-- True\n-- (4.78 secs, 1,940,781,632 bytes)\n-- \u03bb> libreDeCuadrados3 9699690\n-- True\n-- (0.01 secs, 561,400 bytes)\n-- \u03bb> libreDeCuadrados4 9699690\n-- True\n-- (0.01 secs, 568,160 bytes)\n-- \u03bb> libreDeCuadrados5 9699690\n-- True\n-- (0.01 secs, 567,536 bytes)\n--\n-- \u03bb> libreDeCuadrados3 (product (take 30000 primes))\n-- True\n-- (2.30 secs, 2,369,316,208 bytes)\n-- \u03bb> libreDeCuadrados4 (product (take 30000 primes))\n-- True\n-- (6.68 secs, 4,565,617,408 bytes)\n-- \u03bb> libreDeCuadrados5 (product (take 30000 primes))\n-- True\n-- (5.54 secs, 3,411,701,752 bytes)\n<\/pre>\nEl c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n