Números Primos

Código 1

Este código tem com o intuito a geração dos números primos com base no algoritmo Crivo de Eratóstenes.

-- Apenas verifica para os números ímpares, já que todos os pares são múltiplos de 2
primos x = 2 : primosrec (limite x) [3,5..x]

-- O limite é calculado usando a raiz quadrada no maior número que se prende saber se é primo
limite = truncate . sqrt . fromIntegral

-- Filtra recursivamente a lista de primos até se atingir o limite.
primosrec lim p@(x:xs) | lim < x = p
                       | otherwise = x : primosrec lim (filter (not.multiplos) xs)
   where multiplos y = (y `mod` x) == 0

Utilização

Para utilizar basta indicar até que número se pretende obter os números primos.

primos 50
-- irá devolver [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

Código 2

-- Lista infinita de todos os primos
todosprimos = 2 : (filter primo [3,5..])
  where
    primo n = all (/= 0) . map (n  `mod`) $ [2 .. raiz n]
    raiz = truncate . sqrt . fromIntegral

-- Lista os n primeiros primos
primeirosprimos n = take n todosprimos

-- Lista todos os primos que sejam <= n
listaprimos n | n >= 2    = takeWhile (<= n) todosprimos
              | otherwise = []

Utilização

Aplicando as funções primeirosprimos e listaprimos, teremos o exemplo seguinte:

primeirosprimos 10
  -- devolve: [2,3,5,7,11,13,17,19,23,29]
listaprimos 40
  -- devolve: [2,3,5,7,11,13,17,19,23,29,31,37]