Números primos - Crivo de Eratóstenes

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

Números primos - Crivo de Eratóstenes

Mensagempor filipematos em Segunda Set 12, 2011 10:34 pm

Já algum tempo que não posto uma dúvida sobre python aqui no fórum. O meu problema é o seguinte: Elaborei um algoritmo em python baseado no crivo de Eratóstenes para descobrir os números primos dentro de um determinado intervalo. Ele funciona eficientemente e rapidamente para números pequenos. O meu problema consegue-se com números grandes pois fica muito lento.
Há alguma solução para o meu problema ou por muito eficiente que seja o meu algoritmo não vou conseguir gerar números primos rapidamente?
Ordem de grandeza: sqrt(600851475143)
"If I have seen further than others, it is by standing upon the shoulders of giants" - Isaac Newton

“We build too many walls and not enough bridges.” - Isaac Newton
filipematos
down-Quark!
down-Quark!
 
Mensagens: 280
Registado: Sábado Jun 25, 2011 4:48 pm
Localização: Lisboa

Re: Números primos - Crivo de Eratóstenes

Mensagempor Tharis em Segunda Set 12, 2011 10:40 pm

Um crivo de geração de números primos mais eficiente que o de Eratóstenes é o Crivo de Atkin. Não sei se é aquilo que procuras, mas dá uma olhadela. ;)
Avatar do utilizador
Tharis
up-Quark!
up-Quark!
 
Mensagens: 387
Registado: Quinta Out 23, 2008 4:26 pm

Re: Números primos - Crivo de Eratóstenes

Mensagempor filipematos em Terça Set 13, 2011 11:14 am

Acho que é o que estava à procura, no entanto, depois de ter dado uma olhadela na wikipedia não consegui entender o algoritmo. Pesquisei na web mas apenas consigo encontrar implementações em C.
"If I have seen further than others, it is by standing upon the shoulders of giants" - Isaac Newton

“We build too many walls and not enough bridges.” - Isaac Newton
filipematos
down-Quark!
down-Quark!
 
Mensagens: 280
Registado: Sábado Jun 25, 2011 4:48 pm
Localização: Lisboa


Voltar para Pitónica

Quem está ligado

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

cron