Verificar número primo em Python
Nesta lição, você vai verificar se um número é primo testando divisores apenas até a sua raiz quadrada.
Introdução
O problema
Números primos estão por trás da criptografia na internet, das tabelas hash e de muitos quebra-cabeças. Verificar se um número é primo testando cada divisor até o próprio número funciona para 29, mas fica muito lento para números grandes. Uma pequena ideia deixa a verificação bem mais rápida.
Pense assim
Procurar divisores é como tentar montar um retângulo completo com azulejos. 36 azulejos formam 1×36, 2×18, 3×12, 4×9 e 6×6. Depois do quadrado (6×6), os mesmos retângulos voltam, só que virados, então não há nada novo para achar além da raiz quadrada. Já 29 azulejos só formam 1×29, então 29 é primo.
number > 1🚪 Só números maiores que 1 podem ser primosdivisor * divisor <= number🪞 Pare no quadrado: daí em diante só tem repetiçãonumber % divisor == 0🔍 Fechou um retângulo completo: não é primodivisor += 1➡️ Tente a próxima larguraUm número primo é um número inteiro maior que 1 cujos únicos divisores positivos são 1 e ele mesmo.
Pontos-chave
is_prime = number > 1começa com False para 0, 1 e números negativos, que nunca são primos.while divisor * divisor <= number and is_prime:para na raiz quadrada ou assim que um divisor aparece.number % divisor == 0significa quedivisordivide o número sem deixar resto.- Para 29, o laço só testa 2, 3, 4 e 5 antes de poder dizer que o número é primo.
Quando usar?
- Quebra-cabeças e exercícios com números, como listar primos ou achar fatores primos.
- Aprender por que parar cedo e verificar só até um limite deixa os laços mais rápidos.
- Validar entradas em ferramentas de matemática.
Quando não é preciso
- Listar todos os primos até um limite grande: o Crivo de Eratóstenes é muito mais rápido que verificar cada número.
- Criptografia com números de centenas de algarismos: sistemas reais usam testes probabilísticos.
Código de exemplo
number = 29
is_prime = number > 1
divisor = 2
while divisor * divisor <= number and is_prime:
if number % divisor == 0:
is_prime = False
divisor += 1
print(f"{number} is prime: {is_prime}")
Resultado da execução
29 is prime: True
Explicação do código
O laço só precisa testar divisores enquanto divisor * divisor <= number. Isso porque, se n tiver um divisor maior que a raiz quadrada de n, ele vem acompanhado de um divisor menor que o laço já testou. Assim a complexidade cai para O(√n), e o resultado mostra que 29 é primo.
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Tente modificar o código seguindo as sugestões abaixo. Mudar o código e observar o resultado ajuda você a entender muito mais do que só ler.
- Mude os dados de entrada e tente prever o resultado antes de executar.
- Adicione uma verificação para dados vazios ou inválidos.
- Coloque a lógica em uma função separada e teste com vários conjuntos de dados.
Erros comuns
Tratar 1 como primo
1 tem um só divisor, então não é primo. Verifique number > 1 primeiro.
is_prime = True # 1 would be reported as prime
is_prime = number > 1
Fazer o laço ir até o próprio número
Dá a resposta certa, mas testa muito mais divisores do que o necessário.
for divisor in range(2, number):
while divisor * divisor <= number:
Terminou esta lição?
Marque como aprendida para acompanhar seu progresso.
Pratique com um desafio
Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.
- Verificação de Número Primo Decida se um número é primo. Fácil
- Maior Fator Primo Encontre o maior número primo que divide um inteiro positivo. Médio
- Liste Primos com um Crivo Encontre números primos até um limite marcando múltiplos compostos. Médio