Página 1 de 1

Crivo de Eratosthenes

MensagemEnviado: Terça Dez 23, 2008 1:52 pm
por Tharis
Acho que toda a gente conhece o famoso Crivo de Eratosthenes. É um algoritmo que serve para gerar todos os números primos num intervalo [2,n] qualquer. Funciona simplesmente assim:

1. - Escrever todos os numeros de 2 a N.
2. - Riscar todos os múltiplos de 2.
3. - O próximo número que não foi riscado é um número primo.
4. - Riscar todos os múltiplos desse número.
5. - Repetir 3 e 4 até não haver mais números a riscar.

Pedir para fazer isto seria muito simples, portanto, o desafio será fazer o Crivo em apenas uma linha! :D

E sim, é MUITO possível.

Cumps

Re: Crivo de Eratosthenes

MensagemEnviado: Terça Dez 23, 2008 4:33 pm
por jap
Boa! mais um desafio oneliner de um problema clássico para praticarem durante a época festiva! :xrazz:

Re: Crivo de Eratosthenes

MensagemEnviado: Terça Fev 03, 2009 10:01 pm
por miranda_henrique
Olá a todos!

Acho que descobri uma forma de resolver este problema.
Certamente não e a forma mais bonita mas funciona.

Código: Seleccionar Todos
print reduce(lambda lista1,lista2: filter(lambda x: x in lista1, lista2), map(lambda y: filter(lambda x: x == y or x % y, range(2,40)), range(2,40)))


Este código dá os primos entre 2 e 40. Para outros valores basta alterar o 40 pelo numero pretendido n.
Para tornar o programa mais rápido pode-se em vez de por n no ultimo range pode-se por sqrt{40} que dá o mesmo resultado.