Teste de Primalidade até sqrt(n)
Verifique um único número com eficiência.
Teste de Primalidade até sqrt(n) é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 2 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.
A questão dos primos
Uma habilidade matemática fundamental é decidir se um único número é primo. Um número primo tem exatamente dois divisores: um e ele mesmo. Vamos testá-lo rapidamente. 🔍
A verificação ingênua
Você poderia tentar dividir n por todos os números de 2 até n menos 1. É correto, mas dolorosamente lento quando n é grande.
O truque da raiz quadrada
A ideia principal é a seguinte: você só precisa testar divisores até a raiz quadrada de n. Depois disso, nenhum fator novo pode aparecer.
Por que a raiz quadrada basta
Os divisores aparecem em pares cujo produto é n. Se ambos estivessem acima da raiz quadrada, seu produto excederia n, o que é impossível.
O limite do laço
Itere i a partir de 2 enquanto i vezes i permanecer menor ou igual a n. Usar i*i evita erros de ponto flutuante causados por sqrt com inteiros grandes.
while i * i <= n:
...Trate os casos pequenos
Números menores que 2 nunca são primos, portanto rejeite-os logo no início. Essa verificação mantém seu laço principal limpo e correto.
if n < 2:
return FalseA função completa
Reúna tudo: verifique os valores pequenos e depois examine os possíveis divisores até a raiz. Qualquer divisão exata significa que n é composto.
def is_prime(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return TrueAcelere o processo
Verifique 2 separadamente e teste apenas números ímpares. Ignorar os pares reduz aproximadamente pela metade o trabalho, sem complexidade adicional.
if n % 2 == 0:
return n == 2O custo de tempo
Esse teste executa em tempo O(sqrt n). Para um único número de até um bilhão, isso representa apenas cerca de 30.000 operações simples.
Um número, não vários
O teste pela raiz quadrada é excelente para uma ou poucas consultas. Se você precisar verificar primalidade em um intervalo inteiro, um crivo será muito mais rápido.
Evite a armadilha da raiz quadrada
Comparar com i*i em vez de math.sqrt evita erros de arredondamento que podem aceitar ou rejeitar incorretamente números no limite.
Verificação rápida
Confirme o limite que torna esse teste rápido.
Recapitulação
Agora você consegue testar a primalidade de um número em tempo O(sqrt n), verificar valores pequenos, ignorar os pares e usar i*i para manter a exatidão. ✅
Perguntas Frequentes
A aula “Teste de Primalidade até sqrt(n)” é grátis?
Sim — o texto completo de “Teste de Primalidade até sqrt(n)” é 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 “Teste de Primalidade até sqrt(n)”?
Verifique um único número com eficiência. 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 2 de 4.
Quanto tempo leva a aula “Teste de Primalidade até sqrt(n)”?
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