El 2019 es semiprimo

José A. Alonso

03-01-2019

Un número semiprimo es un número natural que es producto de dos números primos no necesariamente distintos. Por ejemplo, 26 es semiprimo (porque 26 = 2x13) y 49 también lo es (porque 49 = 7x7).

Definir las funciones

esSemiprimo :: Integer -> Bool
semiprimos  :: [Integer]

tales que + (esSemiprimo n) se verifica si n es semiprimo. Por ejemplo,

esSemiprimo 26          ==  True
esSemiprimo 49          ==  True
esSemiprimo 8           ==  False
esSemiprimo 2019        ==  True
esSemiprimo (21+10^14)  ==  True

semiprimos es la sucesión de números semiprimos. Por ejemplo,

take 10 semiprimos   ==  [4,6,9,10,14,15,21,22,25,26]
semiprimos !! 579    ==  2019
semiprimos !! 10000  ==  40886

Soluciones

import Data.Numbers.Primes

-- 1ª definición de esSemiprimo
-- ============================

esSemiprimo :: Integer -> Bool
esSemiprimo n =
  not (null [x | x <- [n,n-1..2],
                 primo x,
                 n `mod` x == 0,
                 primo (n `div` x)])

primo :: Integer -> Bool
primo n = [x | x <- [1..n], n `mod` x == 0] == [1,n]

-- 2ª definición de esSemiprimo
-- ============================

esSemiprimo2 :: Integer -> Bool
esSemiprimo2 n =
  not (null [x | x <- [n-1,n-2..2],
                 isPrime x,
                 n `mod` x == 0,
                 isPrime (n `div` x)])

-- 3ª definición de esSemiprimo
-- ============================

esSemiprimo3 :: Integer -> Bool
esSemiprimo3 n =
  not (null [x | x <- reverse (takeWhile (<n) primes),
                 n `mod` x == 0,
                 isPrime (n `div` x)])

-- 4ª definición de esSemiprimo
-- ============================

esSemiprimo4 :: Integer -> Bool
esSemiprimo4 n =
  length (primeFactors n) == 2

-- Comparación de eficiencia
-- =========================

--    λ> esSemiprimo 5001
--    True
--    (1.90 secs, 274,450,648 bytes)
--    λ> esSemiprimo2 5001
--    True
--    (0.07 secs, 29,377,016 bytes)
--    λ> esSemiprimo3 5001
--    True
--    (0.01 secs, 1,706,840 bytes)
--    λ> esSemiprimo4 5001
--    True
--    (0.01 secs, 142,840 bytes)
--
--    λ> esSemiprimo2 100001
--    True
--    (2.74 secs, 1,473,519,064 bytes)
--    λ> esSemiprimo3 100001
--    True
--    (0.09 secs, 30,650,352 bytes)
--    λ> esSemiprimo4 100001
--    True
--    (0.01 secs, 155,200 bytes)
--
--    λ> esSemiprimo3 10000001
--    True
--    (8.73 secs, 4,357,875,016 bytes)
--    λ> esSemiprimo4 10000001
--    True
--    (0.01 secs, 456,328 bytes)

-- 1ª definición de semiprimos
-- ===========================

semiprimos :: [Integer]
semiprimos = filter esSemiprimo4 [4..]

-- 2ª definición de semiprimos
-- ===========================

semiprimos2 :: [Integer]
semiprimos2 =
  mezclaTodas [[p * q | q <- primes] | p <- primes]

-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como
-- sus elementos son listas infinitas ordenadas. Por ejemplo,
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])
--    [2,3,4,5,6,7,8,9,10,11]
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])
--    [2,4,6,8,9,10,12,14,16,18]
mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = foldr1 xmezcla
  where xmezcla (x:xs) ys = x : mezcla xs ys

mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys)
  | x < y  = x : mezcla xs (y:ys)
  | x == y = x : mezcla xs ys
  | x > y  = y : mezcla (x:xs) ys