O básico que a maioria explica errado
Número primo é um número inteiro maior que 1 que só é divisível por 1 e por ele mesmo. Pronto. Isso é tudo. O problema é que quase todo tutorial começa aí e para aí, como se entender a definição significasse saber usar o conceito na prática. Não significa. Vou explicar de um jeito que faz sentido quando você precisa realmente trabalhar com isso, não só passar numa prova de matemática do ensino médio.
O que é numero primo na prática
A definição formal diz que um número primo p satisfaz: p > 1 e seus únicos divisores positivos são 1 e p. Mas na prática você não fica testando divisores um por um manualmente. Ninguém faz isso. Você usa algoritmos de teste de primalidade e isso muda completamente a forma como pensa sobre o assunto. Os primeiros primos são 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. O 2 é o único primo par. Isso parece óbvio até você tentar escrever um código que verifica primalidade e esquece de tratar o 2 como caso especial, aí seu loop de verificação falha silenciosamente ou entra em loop infinito dependendo da implementação. Já vi isso acontecer em produção.
Como verificar se um número é primo de verdade
O teste mais simples é a divisão Trial Division. Você testa se algum número de 2 até a raiz quadrada do número divide ele exatamente. Se nenhum dividir, é primo. A raiz quadrada é importante aqui porque se um número tiver um fator maior que sua raiz, o fator complementár precisa ser menor que a raiz, então você já teria encontrado. Implementação ingênua em Python:
def eh_primo(n): if n
2: return False if n == 2: return True if n % 2 == 0: return False for i in range(3, int(n0.5) + 1, 2): if n % i == 0: return False return True Isso funciona bem para números pequenos. Até uns 10 dígitos, sem problemas. A partir daí, você percebe que testar divisão por todos os ímpares até a raiz quadrada começa a ficar lento demais para o que você precisa. Um número de 20 dígitos nesse algoritmo pode levar segundos ou minutos dependendo da máquina.
O problema que eu encontrei e o workaround
Trabalhando com criptografia RSA há alguns anos, precisei gerar pares de números primos grandes (512 bits cada) para testes de performance. O algoritmo trial division simplesmente não entrava na conversa. Levaria mais tempo que a idade do universo pra confirmar primalidade de números daquele tamanho. A solução foi usar o teste de Miller-Rabin, que é probabilístico mas com margem de erro ajustável. Basicamente, você escolhe bases de teste e cada base que o número passa reduz a chance de ser composto exponencialmente. Com bases suficientes, o erro fica menor que a probabilidade de seu hardware ter um defeito cósmico aleatório.
Em Python, a biblioteca padrão já resolve isso: import sympy sympy.isprime(1000000007) retorna True, usa Miller-Rabin otimizado
👉 Clique no botão abaixo para saber mais sobre o assunto!
Se você não quer depender de bibliotecas externas, existe uma variante determinística do Miller-Rabin para números abaixo de 3.317 bilhões que usa bases fixas específicas. Para números menores que 2^64, as bases [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] são suficientes e o resultado é 100% determinístico, sem nenhuma probabilidade envolvida.
O que ninguém te conta sobre primos
Uma coisa contra-intuitiva: a distribuição dos números primos não é aleatória, mas também não segue nenhum padrão simples o suficiente pra prever onde o próximo vai aparecer. A função pi(x), que conta quantos primos existem até x, é estudada há séculos e a conjectura do primos gêmeos (existem infinitos pares de primos cuja diferença é 2) ainda não foi provada. Isso significa que sim, existem problemas elementares sobre primos que matemáticos profissionais ainda não resolveram. Outro ponto importante: a função.phi de Euler, usada extensivamente em criptografia, depende diretamente da fatoração prima. Se você consegue fatorar um número composto grande em seus fatores primos, consegue calcular phi e quebrar RSA. Esse é o problema central que torna os primos úteis na prática. Números grandes que são produto de dois primos grandes são fáceis de multiplicar mas extremamente difíceis de fatorar de volta. Essa assimetria é a base de gran parte da segurança digital moderna.
Limitações reais que você precisa conhecer
O teste de Miller-Rabin, mesmo na versão determinística para 64 bits, exige implementação cuidadosa. Multiplicações de números grandes podem estourar o tamanho padrão de variáveis inteiras. Em Python isso não é problema porque o interpretador manejaBigIntegers automaticamente, mas em C, Java ou Go você precisa usar aritmética de módulo com BigInteger ou bibliotecas especializadas. Implementar multiplicações modulares seguras de cabeça é onde a maioria dos bugs entra. Para números acima de 64 bits, o teste volta a ser probabilístico. Você escolhe o número de rodadas e o erro cai como 1/4 por rodada. 20 rodadas dão erro menor que 10^-12. Isso é suficiente para a maioria dos usos, mas se você está construindo algo onde um falso positivo causaria prejuízo real, precisa saber disso e documentar.
Uma alternativa quando você precisa de muitos primos de uma vez, como em tabelas hash ou geradores, é usar uma peneira de Eratóstenas. Ela pré-calcula todos os primos até um limite N em tempo O(N log log N), que é praticamente linear na prática. Para gerar milhares de primos pequenos, isso é dramaticamente mais rápido que chamar teste de primalidade individualmente em cada número.
Resumo funcional
Para números até 10^6: peneira de Eratóstenas. Para números isolados até 2^64: Miller-Rabin determinístico com bases fixas. Para números acima de 2^64: Miller-Rabin probabilístico com 20+ rodadas ou bibliotecas como GMP + mpz_probab_prime_p. Trial division só para números pequenos ou didática. Se precisar de geração de primos grandes para criptografia, use uma biblioteca estabelecida, não escreva seu próprio gerador. Já vi gente fazer isso e o resultado eram primos que não eram primos porque o teste tava incompleto. O conceito em si é simples. A parte difícil é aplicar corretamente fora do contexto acadêmico.
