n (lcand' n))lcand' n = [2..(div n 2) - 1]E podemos avaliar numeros com respeito a sua primalidade usando a nova versao:> primo' 35 False (427 reductions, 628 cells)> primo' 36 False (173 reductions, 267 cells)> primo' 859963392 False (173 reductions, 273 cells)Agora vejamos algumas comparacoes entre as duas versoes.Primeiro, quando aplicamos as duas funcoes para numeros nao primos, verifica-se um desempenho semelhante:> primo 1048576 False (116 reductions, 188 cells)> primo' 1048576 False (173 reductions, 270 cells)Mas com numeros primos, ja percebe-se uma boa diferenca 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 reducoes da lista de candidatos. Rapidamente podemos perceber que temos mais candidatos do que precisamos. Dos numeros pares, basta usar o 2. Assim, podemos trabalhar apenas com a lista formada pelo 2 e os numeros impares.primo'' n = not (tem_divisor n (lcand'' n))lcand'' n = [2] ++ [3,5..(div n 2) - 1]E novamente, a avaliacao, no leva a perceber ganhos.> primo'' 1048583 True (21.233.886 reductions, 31180614 cells, 31 garbage collections)Bom, isto parece animado! Que novas reducoes podemos fazer na lista de candidatos?Vamos medir o tamanho das listas que temos usado para o numero 1.048.583?> length (lcand 1048583) 1.048.581 > length (lcand' 1048583) 524.289 > length (lcand'' 1048583) 262.145Uma nova inspecao nos leva a conclusao 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 versao da lista de candidatos:lcand''' n = [2] ++ [3,5..truncate(sqrt n)]e determinar o tamanho desta lista para o nosso numero exemplo:> length (lcand''' 1048583) 512 E agora parece que temos uma excelente melhoria no desempenho.Poderiamos agora ver o comportamento da nova versao para a funcao primo:primo''' n = not (tem_divisor n (lcand''' n))infelizmente a tentativa de usa-la, chegamos ao seguinte entrave:> primo''' 1048583ERROR - Unresolved overloading*** Type : (Floating a, Integral a, RealFrac a) => Bool*** Expression : primo''' 1048583e nossa expectativa fica parcialmente frustada. Depois iremos conversar melhor sobre este tipo de problema, por enquanto vamos contornar de uma maneira simples, usando a avaliacao direta da definicao:> 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 avaliacao da primalidade do numero 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 reducoes anteriores eram da ordem de n/2, neste caso obtivemos uma reducao em torno de sqrt n * 10.Sera que ainda podemos reduzir esta lista de candidatos?A pista e a seguinte: a lista de candidatos pode ser composta apenas por numeros primos, certo?Encerramos esta postagem chamando atencao para uma certa similaridade entre a solucao adotada no tratamento dos numeros feios e os numeros primos. Nos dois casos, geramos uma