Crivo de Eratóstenes
Liste todos os primos até N em tempo quase linear.
Crivo de Eratóstenes é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Primos em massa
Às vezes, você precisa de todos os primos até N, não apenas de uma verificação. O Crivo de Eratóstenes encontra todos eles em uma única varredura. 🧹
A grande ideia
Comece supondo que todos os números são primos. Depois, risque os múltiplos de cada primo encontrado, deixando para trás apenas os primos verdadeiros.
Configure as marcações
Crie uma lista booleana em que o índice i indique se i é primo. Esse vetor é a tela onde o crivo será construído.
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = FalsePercorra os candidatos
Avance i. Na primeira vez que chegar a um número ainda marcado como True, ele deverá ser um novo primo sem fator menor.
Risque os múltiplos
Para cada primo i, marque 2i, 3i, 4i e assim por diante como não primos. Esses múltiplos claramente têm i como divisor.
for j in range(i * i, n + 1, i):
is_prime[j] = FalseComece em i ao quadrado
Comece a riscar em i*i, não em 2i. Todo múltiplo menor já foi removido por um primo anterior, portanto ignore-o.
Pare na raiz
Você só precisa executar o crivo enquanto i*i permanecer menor ou igual a N. Depois da raiz quadrada, toda marcação True restante já representa um primo.
O crivo completo
Combine a varredura externa com o processo interno de riscar. Depois do laço, todo índice ainda marcado como True será um primo confirmado.
for i in range(2, int(n ** 0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = FalseColete os primos
Leia as marcações concluídas em uma lista usando uma compreensão. Agora você tem todos os primos até N prontos para consultas rápidas.
primes = [i for i, p in enumerate(is_prime) if p]Por que é rápido
O crivo executa em cerca de O(n log log n), quase linear. É por isso que ele supera com folga os testes repetidos de números individuais.
Atenção à memória
O vetor de marcações usa uma quantidade de memória proporcional a N. Para limites muito grandes, verifique seu limite de espaço antes de alocar.
Verificação rápida
Relembre a pequena otimização no laço interno.
Recapitulação
Agora você consegue construir um crivo para listar todos os primos até N em tempo quase linear, começando cada primo em i*i e parando na raiz. ✅
Perguntas Frequentes
A aula “Crivo de Eratóstenes” é grátis?
Sim — o texto completo de “Crivo de Eratóstenes” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Crivo de Eratóstenes”?
Liste todos os primos até N em tempo quase linear. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Crivo de Eratóstenes”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- GCD, LCM e o Algoritmo de Euclides
- Teste de Primalidade até sqrt(n)
- Crivo de Eratóstenes
- Fatoração Prima e Divisores