Números Primos - I

Uma maneira simples de verificar se um número é primo, se baseia na própria definição:

"Um número n é primo quando seus únicos divisores são a unidade e o próprio n"

Assim, basta que um número n possua pelo menos um divisor diferente de 1 e dele mesmo para que não seja primo.

A lista de candidatos a divisores é formada por números maiores que 1 e menores que n, algo como:

lcand n = [2..(n - 1)]

Podemos então construir uma função recursiva que verifica se um número é divisível por algum elemento de uma lista:

tem_divisor n [ ] = False
tem_divisor n (x:xs) = if (mod n x) == 0 then True else tem_divisor n xs

Agora estamos prontos para escrever a função que verifica se um número é primo:

primo n = not (tem_divisor n (lcand n))

Vejamos alguns exemplos de uso:

> primo 35
False
(372 reductions, 620 cells)
> primo 36
False
(116 reductions, 186 cells)
> primo 859963392
False
(116 reductions, 190 cells)

Um rápida reflexão nos levar a perceber que a lista de candidatos tem mais elementos que o necessário. Afinal, não precisamos buscar divisores nos números maiores que a matade de n, certo? Com isso podemos ter uma nova versão.

primo' n = not (tem_divisor n (lcand' n))
lcand' n = [2..(div n 2) - 1]

E podemos avaliar números com respeito à sua primalidade usando a nova versão:

> primo' 35
False
(427 reductions, 628 cells)
> primo' 36
False
(173 reductions, 267 cells)
> primo' 859963392
False
(173 reductions, 273 cells)


Agora vejamos algumas comparações entre as duas versões.

Primeiro, quando aplicamos as duas funções para números não primos, verifica-se um desempenho semelhante:

> primo 1048576
False
(116 reductions, 188 cells)
> primo' 1048576
False
(173 reductions, 270 cells)

Mas com números primos, já percebe-se uma boa diferença no desempenho:

> primo 1048583
True :: Bool
(84.935.121 reductions, 124751350 cells, 126 garbage collections)
> primo' 1048583
True :: Bool
(42.467.534 reductions, 62360646 cells, 63 garbage collections)

Isto nos anima a buscar novas reduções da lista de candidatos. Rapidamente podemos perceber que temos mais candidatos do que precisamos. Dos números pares, basta usar o 2. Assim, podemos trabalhar apenas com a lista formada pelo 2 e os números impares.

primo'' n = not (tem_divisor n (lcand'' n))
lcand'' n = [2] ++ [3,5..(div n 2) - 1]

E novamente, a avaliação, no leva a perceber ganhos.

> primo'' 1048583
True
(21.233.886 reductions, 31180614 cells, 31 garbage collections)

Bom, isto parece animado! Que novas reduções podemos fazer na lista de candidatos?

Vamos medir o tamanho das listas que temos usado para o número 1.048.583?

> length (lcand 1048583)
1.048.581
> length (lcand' 1048583)
524.289
> length (lcand'' 1048583)
262.145

Uma nova inspeção nos leva à conclusão que nossa lista de candidatos a divisores de n ainda pode ser menor. Na verdade, pode-se mostrar que a lista de candidatos tem como limite superior, a raiz quadrada de n.

Assim podemos escrever uma nova versão da lista de candidatos:

lcand''' n = [2] ++ [3,5..truncate(sqrt n)]

e determinar o tamanho desta lista para o nosso número exemplo:

> length (lcand''' 1048583)
512

E agora parece que temos uma excelente melhoria no desempenho.
Poderíamos agora ver o comportamento da nova versão para a função primo:

primo''' n = not (tem_divisor n (lcand''' n))

infelizmente a tentativa de usá-la, chegamos ao seguinte entrave:

> primo''' 1048583
ERROR - Unresolved overloading
*** Type : (Floating a, Integral a, RealFrac a) => Bool
*** Expression : primo''' 1048583

e nossa expectativa fica parcialmente frustada. Depois iremos conversar melhor sobre este tipo de problema, por enquanto vamos contornar de uma maneira simples, usando a avaliação direta da definição:

> not (tem_divisor 1048583 (lcand''' 1048583))
True :: Bool
(41.845 reductions, 59948 cells)

e, como esperado, temos um ganho de desempenho proporcional ao tamanho da nossa nova lista de candidatos.

Abaixo reapresentamos os resultados obtidos com a avaliação da primalidade do número 1.048.583.

primo 1048583 -(84.935.121 reductions, 124751350 cells, 126 garbage collections)
primo' 1048583 -(42.467.534 reductions, 62360646 cells, 63 garbage collections)

primo'' 1048583 -(21.233.886 reductions, 31180614 cells, 31 garbage collections)

primo'''1048583 -(41.845 reductions, 59948 cells)

Enquanto as reduções anteriores eram da ordem de n/2, neste caso obtivemos uma redução em torno de sqrt n * 10.

Será que ainda podemos reduzir esta lista de candidatos?

A pista é a seguinte: a lista de candidatos pode ser composta apenas por números primos, certo?

Encerramos esta postagem chamando atenção para uma certa similaridade entre a solução adotada no tratamento dos números feios e os números primos. Nos dois casos, geramos uma lista de candidatos que são testados.
Esta é uma estratégia geral para solução de problemas, quando desejamos determinar uma lista de elmentos que satisfazem uma determinada propriedade, conhecida como "generate and test", ou "gerar e testar".