Primos o cuadrados de primos
Definir la constante
|
1 |
primosOcuadradosDePrimos :: [Integer] |
cuyos elementos son los número primos o cuadrados de primos. Por ejemplo,
|
1 2 3 4 |
λ> take 20 primosOcuadradosDePrimos [2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49,53] λ> primosOcuadradosDePrimos !! (10^6) 15476729 |
Comprobar con QuickCheck que las lista primosOcuadradosDePrimos y unifactorizables (definida en el ejercicio anterior) son iguales.
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 |
import Test.QuickCheck import Data.Numbers.Primes (primeFactors, primes) -- 1ª solución -- =========== primosOcuadradosDePrimos :: [Integer] primosOcuadradosDePrimos = filter esPrimoOcuadradoDePrimo [2..] esPrimoOcuadradoDePrimo :: Integer -> Bool esPrimoOcuadradoDePrimo n = aux xs where xs = primeFactors n aux [_] = True aux [x,y] = x == y aux _ = False -- 2ª solución -- =========== primosOcuadradosDePrimos2 :: [Integer] primosOcuadradosDePrimos2 = mezcla primes (map (^2) primes) mezcla :: Ord a => [a] -> [a] -> [a] mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys) | otherwise = y : mezcla (x:xs) ys -- Comparación de eficiencia -- ========================= -- λ> primosOcuadradosDePrimos !! (2*10^4) -- 223589 -- (3.08 secs, 9,829,725,096 bytes) -- λ> primosOcuadradosDePrimos2 !! (2*10^4) -- 223589 -- (0.04 secs, 73,751,888 bytes) -- -- λ> primosOcuadradosDePrimos2 !! (5*10^5) -- 7362497 -- (1.29 secs, 3,192,803,040 bytes) -- Propiedad de equivalencia -- ========================= -- La propiedad es prop_equivalencia :: Int -> Property prop_equivalencia n = n >= 0 ==> primosOcuadradosDePrimos2 !! n == unifactorizables !! n -- unifactorizables es la lísta de los números enteros mayores que 1 -- que se pueden escribir sólo de una forma única como producto de -- enteros distintos mayores que uno. Por ejemplo, -- λ> take 20 unifactorizables -- [2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49,53] -- λ> unifactorizables !! 300 -- 1873 unifactorizables :: [Integer] unifactorizables = [n | n <- [2..] , length (sublistasConProducto n [2..n]) == 1] -- (sublistasConProducto n xs) es la lista de las sublistas de la -- lista ordenada estrictamente creciente xs (cuyos elementos son -- enteros mayores que 1) cuyo producto es el número entero n (con n -- mayor que 1). Por ejemplo, -- λ> sublistasConProducto 72 [2,3,4,5,6,7,9,10,16] -- [[2,4,9],[3,4,6]] -- λ> sublistasConProducto 720 [2,3,4,5,6,7,9,10,16] -- [[2,3,4,5,6],[2,4,9,10],[3,4,6,10],[5,9,16]] -- λ> sublistasConProducto 2 [4,7] -- [] sublistasConProducto :: Integer -> [Integer] -> [[Integer]] sublistasConProducto _ [] = [] sublistasConProducto n (x:xs) | x > n = [] | x == n = [[x]] | r == 0 = map (x:) (sublistasConProducto q xs) ++ sublistasConProducto n xs | otherwise = sublistasConProducto n xs where (q,r) = quotRem n x -- La comprobación es -- λ> quickCheck prop_equivalencia -- +++ OK, passed 100 tests. |
Pensamiento
Despacito y buena letra: el hacer las cosas bien importa más que el hacerlas.
Antonio Machado