sem_divisor n [ ] = True
sem_divisor n (x:xs) = if (mod n x) == 0 then False else sem_divisor n xs
--
--
primos = 2:[x|x<-[3,5 ..],
sem_divisor x(takeWhile(<= truncate (sqrt( fromIntegral x)) )primos) ]
A elegância da descrição da lista de primos é o que há de mais importante, principalmente por usar a própria definição de primos. Temos aqui a descrição recursiva de uma lista infinita e, portanto, uma recursão infinita. Ou sejam, nossa lista de candidatos a primos são os números ímpares
x<-[3,5 ..]
e para estes verificamos a existência de divisores, usando para isto apenas um pedaço da lista de primos, ou seja, aqueles que são menores que a raiz quadrada do número considerado.
(takeWhile (<= truncate (sqrt (fromIntegral x)))primos)
Sabemos que a lista primos é infinita e que portanto não é conveniente a sua avaliação por completo, entretanto podemos desejar obter os n primeiros números primos o que pode ser obtido com o uso de take n.
> take 10 primos
[2,3,5,7,11,13,17,19,23,29]
(6948 reductions, 10214 cells)
> take 100 primos
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,
109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,
229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,
479,487,491,499,503,509,521,523,541]
(174196 reductions, 248654 cells)
> take 100 primos
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,
109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,
229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,
479,487,491,499,503,509,521,523,541]
(2437 reductions, 3620 cells)
É importante observar que na segunda vez que usamos > take 100 primos, o número de reduções é bem menor, em decorrência da abordagem que o interpretador dá à avaliação de uma expressão, guardando os resultados de expressões para usos posteriores.
Sabemos que a lista primos é infinita e que portanto não é conveniente a sua avaliação por completo, entretanto podemos desejar obter os n primeiros números primos o que pode ser obtido com o uso de take n.
> take 10 primos
[2,3,5,7,11,13,17,19,23,29]
(6948 reductions, 10214 cells)
> take 100 primos
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,
109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,
229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,
479,487,491,499,503,509,521,523,541]
(174196 reductions, 248654 cells)
> take 100 primos
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,
109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,
229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,
353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,
479,487,491,499,503,509,521,523,541]
(2437 reductions, 3620 cells)
É importante observar que na segunda vez que usamos > take 100 primos, o número de reduções é bem menor, em decorrência da abordagem que o interpretador dá à avaliação de uma expressão, guardando os resultados de expressões para usos posteriores.
Nenhum comentário:
Postar um comentário