Menu Close

El 2019 es semiprimo

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 = 2×13) y 49 también lo es (porque 49 = 7×7).

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 
import Test.QuickCheck
 
-- 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
 
-- Equivalencia de las definiciones de esSemiprimo
-- ===============================================
 
-- La propiedad es
prop_esSemiprimo :: Positive Integer -> Bool
prop_esSemiprimo (Positive n) =
  all (== esSemiprimo n) [f n | f <- [ esSemiprimo2
                                     , esSemiprimo3
                                     , esSemiprimo4
                                     ]]
 
-- La comprobación es
--    λ> quickCheck prop_esSemiprimo
--    +++ OK, passed 100 tests.
 
-- 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)
 
-- Definición de semiprimos
-- ========================
 
semiprimos :: [Integer]
semiprimos = filter esSemiprimo4 [4..]

Pensamiento

Porque toda visión requiere distancia, no hay manera de ver las cosas sin salirse de ellas.

Antonio Machado

Posted in Inicial

5 Comments

  1. frahidzam
    import Data.Numbers.Primes (primeFactors)
     
    esSemiprimo :: Integer -> Bool
    esSemiprimo n
      | length zs == 2 && product zs == n = True
      | otherwise                         = False
      where zs = primeFactors n
     
    semiprimos :: [Integer]
    semiprimos = [a | a <- [1..], esSemiprimo a]
  2. adogargon
    import Data.Numbers.Primes (primeFactors)
     
    esSemiprimo :: Integer -> Bool
    esSemiprimo x = length (primeFactors x) == 2
     
    semiprimos  :: [Integer]
    semiprimos = filter esSemiprimo [4..]
  3. lucsanand
    import Data.Numbers.Primes (isPrime)
     
    esSemiprimo :: Integer -> Bool
    esSemiprimo n =
      x >= 1 && x <= 2
      && filter isPrime (factores n) == factores n
      where x = length (factores n)
     
    factores :: Integer -> [Integer]
    factores n = [x | x <- [2..div n 2], mod n x == 0]
     
    semiprimos  :: [Integer]
    semiprimos = filter esSemiprimo [4..]
  4. luipromor
    import Data.List (nub)
    import Data.Numbers.Primes (primeFactors)
     
    esSemiprimo :: Integer -> Bool
    esSemiprimo x
      | length xs == 1 = ((head xs)^2 == x)
      | otherwise      = length xs == 2 
      where xs = (nub . primeFactors) x 
     
    semiprimos :: [Integer]
    semiprimos = [x | x <- [4..], esSemiprimo x]
  5. javmarcha1
     
    import Data.Numbers.Primes
     
    esSemiprimo :: Integer -> Bool
    esSemiprimo n | length (primeFactors n) == 2 = True
                  | otherwise = False
     
    semiprimos :: [Integer]
    semiprimos = [ x | x <- [1..] , esSemiprimo x]

Escribe tu solución

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