Menu Close

El 2019 es semiprimo

José A. Alonso,

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
Tagged , , , , , , , , , ,

5 Comments

  1. frahidzam
    Responder 
    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
    Responder 
    import Data.Numbers.Primes (primeFactors)
 
esSemiprimo :: Integer -> Bool
esSemiprimo x = length (primeFactors x) == 2
 
semiprimos  :: [Integer]
semiprimos = filter esSemiprimo [4..]
  3. lucsanand
    Responder 
    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
    Responder 
    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
    Responder 
     
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.