O algoritmo mais eficiente para encontrar números primos, é o Crivo de Eratóstenes (assim chamado em honra ao matemático grego que o inventou), que permite obter todos os números primos até um determinados valor n. A ideia é a seguinte :

• Começa-se com a lista [2..n].
• Guarda-se o primeiro elemento da lista (pois é um número primo) e removem-se da cauda da lista todos os múltiplos desse primeiro elemento.
• Continua-se a aplicar o passo anterior à restante lista, até que a lista de esgote.

crivo [] = []
crivo (x:xs) = x : crivo [ n | n <- xs , n `mod` x /= 0 ]

primosAte n = crivo [2..n]

Lista infinita de números primos.

primos = crivo [2..]

Factorização em primos

O Teorema Fundamental da Aritmética (enunciado pela primeira vez por Euclides) diz que qualquer número inteiro (maior que 1) pode ser decomposto num produto de números primos.

Esta decomposição é única a menos de uma permutação.

Exemplo : Com o auxílio da lista de números primos, podemos definir uma função que dado um número (maior do que 1), calcula a lista dos seus fatores primos.

fatoriza :: Integer -> [Integer]
fatoriza n = aux n primos
    where aux l _ = []
          aux n (n:xs)
               | n `mod` x /= 0 = aux n xs
               | otherwise      = x : aux (n `div` x) (x:xs)

> fatoriza 94753
[19,4987]
> fatoriza 9475312
[2,2,2,2,7,11,7691]