Menu Close

Primos o cuadrados de primos

Definir la constante

   primosOcuadradosDePrimos :: [Integer]

cuyos elementos son los número primos o cuadrados de primos. Por ejemplo,

   λ> 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

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

7 soluciones de “Primos o cuadrados de primos

  1. rebgongor
    import Data.Numbers.Primes (primes)
    import Data.List (sort)
     
    primosOcuadradosDePrimos :: [Integer]
    primosOcuadradosDePrimos = 
       sort (take (10^5) primes ++ take (10^5) cuadradosDePrimos)
     
    cuadradosDePrimos :: [Integer]
    cuadradosDePrimos = [x^2 | x <- primes]
  2. juanromsan5
    import Data.Numbers.Primes (isPrime, primeFactors)
    import Data.List (genericLength, nub, group)
     
    primosOcuadradosDePrimos :: [Integer]
    primosOcuadradosDePrimos =
      [x | x <- [2..]
         , isPrime x || factorizacion x == [(head (primeFactors x),2)] ]
     
    factorizacion :: Integer -> [(Integer,Integer)]
    factorizacion x = zip (factoresprimos x) (exponentesOrdenados x)
     
    factoresprimos :: Integer -> [Integer]
    factoresprimos = nub . primeFactors
     
    exponentesOrdenados :: Integer -> [Integer]
    exponentesOrdenados =  map genericLength . group . primeFactors
  3. melgonaco
    import Data.Numbers.Primes (isPrime)
     
    primosOcuadradosDePrimos :: [Integer]
    primosOcuadradosDePrimos = filter primoOcuadrado [2..]
     
    primoOcuadrado :: Integer -> Bool
    primoOcuadrado x = isPrime x || x `elem` (cuadrados x)
     
    cuadrados :: Integer -> [Integer]
    cuadrados x = [b^2 | b <- [1..x], isPrime b]
  4. jostircar1

    Puesto que Rebeca ha solucionado ya el ejercicio, igualmente propongo otra solución alternativa modificando el tipo de la función, simplemente por experimentar. Sería con una función de un entero en una lista de enteros.

    import Data.Numbers.Primes
    import Data.List
     
    primosOcuadradosDePrimos :: Int -> [Integer]
    primosOcuadradosDePrimos y =
      take y (sort (take y [n^2 | n <- primes] ++ take y [x | x <- primes]) )
  5. Fernando Carreño Navas
    -- fercarnav
     
    import Data.Numbers.Primes (isPrime)
     
    primosOcuadradosDePrimos :: [Integer]
    primosOcuadradosDePrimos  = [n | n <- [2..], isPrime n || cuadradoPrimo n]
     
    cuadradoPrimo :: Integer -> Bool
    cuadradoPrimo n
      | fromInteger (round x) == x = isPrime (round x)
      | otherwise = False
       where x = sqrt (fromInteger n)

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.