Número Primo E Composto

Como distinguir na prática

O método mais direto que já vi funcionar sem enrolação é dividir o número por primos sequenciais até a raiz quadrada dele. Se sobrar resto em todas as tentativas, é primo. Se um desses divisores fechar exato, é composto. Achei esse caminho padrão porque funciona para números pequenos e médios, mas tem uma pegadinha que todo mundo ignora até errar feio.

número primo e composto: o que você realmente precisa saber

A definição de livro diz que primo tem exatamente dois divisores positivos, e composto tem mais do que dois. Isso é verdade, mas na prática eu vejo gente achando que 51 é primo porque ele não divide por 2, 3, 5 ou 7 de forma óbvia. 51 é 3 vezes 17. Erro comum. O problema é que muitos param a verificação antes da raiz quadrada sem perceber, especialmente quando o número tem fatores grandes próximos entre si. Eu montei um script simples em Python que roda teste de divisibilidade até int(numero0.5) + 1, usando apenas os primos gerados previamente. O script corta o tempo de verificação manual de minutos para frações de segundo em números abaixo de um milhão. Para números acima disso, a coisa muda de figura e chega um ponto em que mesmo esse método fica lento demais.

O truque que ninguém conta é que você não precisa testar todos os ímpares. Basta testar os primos. Gerar uma peneira de Eratóstenes até a raiz quadrada do número-alvo e usar esses valores como únicos candidatos já resolve 90% dos casos que eu encontro no dia a dia. Restam aqueles números quase-primos, onde dois fatores grandes se multiplicam e ficam perto da raiz quadrada. Aí o teste por tentativa direta ainda é a única saída confiável, a menos que você recorra a testes probabilísticos. Existem testes como Miller-Rabin que aceleram a verificação para números enormes, mas eles são probabilísticos e dão chance de falso positivo, ainda que pequena. Para quem trabalha com criptografia ou fatoração séria, o recomendado é combinar Miller-Rabin com o algoritmo de Pollard rho para quebrar os fatores compostos. Eu já vi isso economizar horas em comparação com a divisão ingênua.

A parte chata é que números perfeitos, amicáveis e outros subtipos fogem completamente desse raciocínio simples. Dizer se um número é primo ou composto é uma coisa. Classificar se ele é perfeito, abundante ou déficitário é outra conversa. Eu já perdi tempo tentando aplicar critérios de primalidade em problemas que na verdade eram sobre divisibilidade ou somatório de divisores, porque o enunciado estava mal formulado. Outro erro frequente é tratar o número 1 como primo. Não é. Ele é unidade. Tem exatamente um divisor positivo, então não se encaixa nem na definição de primo nem na de composto. Se um problema pede para listar primos abaixo de 10 e você inclui o 1, já era. A lista errada costuma derrubar questões inteiras em provas e concursos.

Para números compostos, a fatoração em primos é única. Isso é o teorema fundamental da aritmética e é o que sustenta tudo, desde simplificação de frações até o RSA. Você pode passar o número por qualquer método que for, mas o resultado final sempre converge para os mesmos fatores primos. Eu já vi gente trocar a ordem dos passos e achar que chegou a um resultado diferente. Não chega. A fatoração é única, ponto. Se você está começando agora, use a peneira de Eratóstenes até 1000 para treinar. Ela dá uma intuição rápida de como os primos se espalham e onde eles acabam rareando. Para numbers acima de 10 mil, dependa de um gerador de primos assistido por software. A mão humana não escala bem nesse intervalo sem cometer falhas.

O que eu recomendo de verdade é um script básico que gera os primos via Eratóstenes e depois testa divisibilidade apenas com eles. O código abaixo faz exatamente isso para números até cerca de 100 milhões, com tempo de resposta geralmente abaixo de um segundo em uma máquina comum. Acima disso, o ideal é migrar para Miller-Rabin.

def primos_ate(n):
    crivo = [True] * (n + 1)
    crivo[0] = crivo[1] = False
    for p in range(2, int(n0.5) + 1):
        if crivo[p]:
            for i in range(p * p, n + 1, p):
                crivo[i] = False
    return [p for p, is_p in enumerate(crivo) if is_p]

def eh_primo(num, primos):
    if num < 2:
        return False
    for p in primos:
        if p * p > num:
            break
        if num % p == 0:
            return False
    return True

primos = primos_ate(100000)
print(eh_primo(51, primos))
print(eh_primo(997, primos))

Esse modelo resolve a maioria das situações práticas de cálculo manual assistido e ainda deixa claro onde a divisão falha, porque você vê exatamente qual primo testou e em qual ponto parou. Quando o número é primo, o loop termina quando p multiplicado por si mesmo ultrapassa num. Quando é composto, ele para no primeiro fator encontrado. As duas trajetórias são visíveis e isso ajuda a diagnosticar erros sem depender de adivinhação. Se o objetivo é só classificar números e não fatorá-los, esse script já é suficiente. Se precisa fatorar de verdade, aí entra a parte mais trabajosa, que é acumular os divisores encontrados e continuar dividindo o quociente até reduzir tudo a primos. Eu faço isso rodando o mesmo crivo e aplicando divisão repetida em cada fator achado. O resultado é a decomposição canônica, sem margem para ambiguidade.

Resumindo sem resumo: entenda a raiz quadrada como limite, use primos como únicos candidatos, evite confundir 1 com primo e escala para testes probabilísticos quando os números saem do alcance do crivo simples. O resto é rotina.