Mayor semiprimo menor que n
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 x 13) y 49 también lo es (porque 49 = 7 x 7).
Definir la función
mayorSemiprimoMenor :: Integer -> Integer
tal que (mayorSemiprimoMenor n) es el mayor semiprimo menor que n (suponiendo que n > 4). Por ejemplo,
mayorSemiprimoMenor 27 == 26 mayorSemiprimoMenor 50 == 49 mayorSemiprimoMenor 49 == 46 mayorSemiprimoMenor (10^6) == 999997
Soluciones
import Data.Numbers.Primes -- 1ª definición -- ============= mayorSemiprimoMenor :: Integer -> Integer mayorSemiprimoMenor n = head [x | x <- [n-1,n-2..2], semiPrimo x] semiPrimo :: Integer -> Bool semiPrimo 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 -- ============= mayorSemiprimoMenor2 :: Integer -> Integer mayorSemiprimoMenor2 n = head [x | x <- [n-1,n-2..2], semiPrimo2 x] semiPrimo2 :: Integer -> Bool semiPrimo2 n = not (null [x | x <- [n-1,n-2..2], isPrime x, n `mod` x == 0, isPrime (n `div` x)]) -- 3ª definición -- ============= mayorSemiprimoMenor3 :: Integer -> Integer mayorSemiprimoMenor3 n = head [x | x <- [n-1,n-2..2], semiPrimo3 x] semiPrimo3 :: Integer -> Bool semiPrimo3 n = not (null [x | x <- reverse (takeWhile (<n) primes), n `mod` x == 0, isPrime (n `div` x)]) -- 4ª solución mayorSemiprimoMenor4 :: Integer -> Integer mayorSemiprimoMenor4 n = head [ p | p <- [n-1,n-2..2] , (length . primeFactors) p == 2] -- Comparación de eficiencia -- ========================= -- λ> mayorSemiprimoMenor 2000 -- 1994 -- (2.32 secs, 329,036,016 bytes) -- λ> mayorSemiprimoMenor2 2000 -- 1994 -- (0.13 secs, 81,733,304 bytes) -- λ> mayorSemiprimoMenor3 2000 -- 1994 -- (0.02 secs, 0 bytes) -- λ> mayorSemiprimoMenor4 2000 -- 1994 -- (0.01 secs, 0 bytes) -- -- λ> mayorSemiprimoMenor3 300000 -- 299995 -- (1.16 secs, 484,484,632 bytes) -- λ> mayorSemiprimoMenor4 300000 -- 299995 -- (0.01 secs, 0 bytes)