Crivo de Eratosthenes

Secção dedicada à linguagem de programação favorita dos quarkianos: Python!

Crivo de Eratosthenes

Mensagempor Tharis em Terça Dez 23, 2008 1:52 pm

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
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Crivo de Eratosthenes

Mensagempor jap em Terça Dez 23, 2008 4:33 pm

Boa! mais um desafio oneliner de um problema clássico para praticarem durante a época festiva! :xrazz:
José António Paixão
Departamento de Física da FCTUC
Avatar do utilizador
jap
Site Admin
Site Admin
 
Mensagens: 6790
Registado: Quinta Nov 09, 2006 9:34 pm
Localização: Univ. de Coimbra

Re: Crivo de Eratosthenes

Mensagempor miranda_henrique em Terça Fev 03, 2009 10:01 pm

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.
Visitem:
Blog da SAC: sac-aac.blogspot.com
Blog do Carro da Queima das Fitas 2011 de Física/Engenharia Física: feitosaobif.blogspot.com
Blog de humor avulso: maybetheperfectblog.blogspot.com
Avatar do utilizador
miranda_henrique
bottom-Quark!
bottom-Quark!
 
Mensagens: 34
Registado: Sábado Dez 22, 2007 2:51 am
Localização: Barcelos


Voltar para Pitónica

Quem está ligado

Utilizadores a navegar neste fórum: Nenhum utilizador registado e 1 visitante

cron