Página 1 de 1

Números primos - Crivo de Eratóstenes

MensagemEnviado: Segunda Set 12, 2011 10:34 pm
por filipematos
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)

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

MensagemEnviado: Segunda Set 12, 2011 10:40 pm
por Tharis
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. ;)

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

MensagemEnviado: Terça Set 13, 2011 11:14 am
por filipematos
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.