Menu Close

Suma de primos menores

La suma de los primos menores que 10 es 2 + 3 + 5 + 7 = 17.

Definir la función

   sumaPrimosMenores :: Integer -> Integer

tal que (sumaPrimosMenores n) es la suma de los primos menores que n. Por ejemplo,

   sumaPrimosMenores 10        ==  17
   sumaPrimosMenores (5*10^5)  ==  9914236195

Nota: Este ejercicio está basado en el problema 10 del Proyecto Euler

Soluciones

import Data.Numbers.Primes (primes)
 
-- 1ª solución
-- ===========
 
sumaPrimosMenores :: Integer -> Integer
sumaPrimosMenores n = sum (takeWhile (<n) primos)
 
-- primos es la lista de los números primos. Por ejemplo,
--    λ> take 12 primos
--    [2,3,5,7,11,13,17,19,23,29,31,37]
primos :: [Integer]
primos = 2 : filter esPrimo [3,5..]
 
esPrimo :: Integer -> Bool
esPrimo n = null [x | x <- [2..(ceiling . sqrt . fromIntegral) n]
                    , n `mod` x == 0]
 
-- 2ª solución
-- ===========
 
sumaPrimosMenores2 :: Integer -> Integer
sumaPrimosMenores2 n = sum (takeWhile (<n) primos2)
 
primos2 :: [Integer]
primos2 = 2 : filter esPrimo2 [3,5..]
 
esPrimo2 :: Integer -> Bool
esPrimo2 x =
  all ((/= 0) . mod x)
  (takeWhile (<= floor (sqrt (fromIntegral x))) primos2)
 
-- 3ª solución
-- ===========
 
sumaPrimosMenores3 :: Integer -> Integer
sumaPrimosMenores3 n = sum (takeWhile (<n) primes)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> sumaPrimosMenores (2*10^5)
--    1709600813
--    (2.56 secs, 1,522,015,240 bytes)
--    λ> sumaPrimosMenores2 (2*10^5)
--    1709600813
--    (0.56 secs, 376,951,456 bytes)
--    λ> sumaPrimosMenores3 (2*10^5)
--    1709600813
--    (0.07 secs, 62,321,888 bytes)

Pensamiento

El movimiento no es nada esencial. La fuerza puede ser inmóvil (lo es en su estado de pureza); mas no por ello deja de ser activa.

Antonio Machado

4 soluciones de “Suma de primos menores

  1. rebgongor
    import Data.Numbers.Primes (primes)
     
    sumaPrimosMenores :: Integer -> Integer
    sumaPrimosMenores n = sum (takeWhile (<n) primes)
  2. jesvazper
    import Data.Numbers.Primes (isPrime)
     
    sumaPrimosMenores :: Integer -> Integer
    sumaPrimosMenores n = sum [ y | y <- [1..n], isPrime y]
  3. javjimord
    sumaPrimosMenores :: Integer -> Integer
    sumaPrimosMenores 1 = 0
    sumaPrimosMenores n
      | primo (n - 1) = (n-1) + sumaPrimosMenores (n - 1)
      | otherwise     = sumaPrimosMenores (n - 1)
     
    primo :: Integer -> Bool
    primo n = [x | x <- [1..n], mod n x  == 0] == [1,n]
  4. jostircar1
    import Data.Numbers.Primes
     
    sumaPrimosMenores :: Integer -> Integer
    sumaPrimosMenores n = sum [x | x <- [1..n], isPrime x, x<n]

Leave a Reply

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