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
Haskell
|
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) |