Números primos - Crivo de Eratóstenes

[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)

[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.

[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.