O que realmente define um número primo
Você já tentou listar todos os primos até 100 de cabeça e percebeu que vai errando no meio do caminho, esquecendo algum ou contando o 1 por acidente. Isso é normal. A definição é simples — um número primo é aquele divisível apenas por 1 e por ele mesmo, sendo maior que 1 — mas a prática exige atenção porque existem armadilhas que todo mundo comete na primeira vez. O teste de divisibilidade mais direto é dividir o número por todos os inteiros entre 2 e a raiz quadrada dele. Se nenhum dividir sem resto, o número é primo. Parece óbvio, mas a parte da raiz quadrada faz uma diferença enorme na performance quando você escala. Testar até o número inteiro em vez de até sua raiz quadrada transforma um cálculo de milissegundos em algo que roda por minutos ou horas, dependendo do tamanho do número.
quais são os números primos que você realmente precisa saber
Os primeiros primos são 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. A partir daí, a lista continua mas já exige consulta ou cálculo programático. O primo 2 é único por ser o único primo par. Todos os outros primos são ímpares, e essa é uma das primeiras coisas que simplifica qualquer algoritmo: depois do 2, você só precisa testar divisores ímpares. Eu once escrevi um script para filtrar primos em um conjunto de dados numéricos e deixei de fora o 2 porque meu código pular tudo par. O resultado foi que eu acabei descartando o único primo par e classifiquei o número 4 como primo em um teste mal feito. Corrigi isso adicionando uma verificação explícita para o 2 antes de qualquer outro loop. Levei cerca de duas horas para encontrar o bug porque o resto da lista estava corretíssima e o erro era sutil demais pra perceber olhando só o resultado final.
O Crivo de Eratóstenes como ferramenta prática
O crivo é o método mais eficiente para gerar todos os primos até um limite N. Você cria uma lista de números de 2 a N, marca os múltiplos de cada primo encontrado e o que sobra é primo. Para N até 10 milhões, esse método roda em questão de segundos em qualquer máquina comum. O problema é que o crivo consome memória proporcional a N. Se você tentar usar ele para primos acima de 1 bilhão, vai precisar de gigabytes de RAM e o tempo de execução cresce junto. Nesse cenário, testes de primalidade probabilísticos como Miller-Rabin são mais adequados, mesmo com a pequena chance teórica de erro que eles carregam.
Existe também o crivo de Atkin, que é mais complexo de implementar mas teoricamente mais rápido para limites muito grandes. Na prática, raramente vale a pena a implementação extra a menos que você esteja rodando em escala industrial. O crivo de Eratóstenes com otimizações básicas — como pular pares e usar um bitarray ao invés de uma lista de booleanos — ainda é o que funciona na maioria dos casos do dia a dia.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Pegadinhas e limitações que ninguém conta
Muita gente inclui o número 1 na lista de primos sem saber que ele não é primo por definição. A definição exige exatamente dois divisores positivos distintos, e o 1 tem apenas um. Isso tem implicações reais na fatoração prima única: se o 1 fosse primo, a fatoração de qualquer número teria infinitas formas possíveis adicionando 1s na frente, e teoremas inteiros da teoria dos números teriam que ser reformulados. Outro ponto que causa confusão é achar que números grandes com aparência de primo realmente são primos. O número 21305024255095005613, por exemplo, parece primo mas é divisível por 7. Sem um teste de primalidade adequado, é quase impossível saber só olhando. Testes determinísticos como ECPP (Elliptic Curve Primality Proving) comprovam primalidade sem margem de erro, mas são lentos. Para uso prático, Miller-Rabin com bases suficientes para o intervalo do seu número dá certeza absoluta na prática, mesmo sendo probabilístico na teoria.
Não existe fórmula fechada que gere apenas números primos de forma eficiente. Fórmulas como n² + n + 41 de Euler geram primos para vários valores consecutivos de n, mas eventualmente falham e não servem como gerador confiável. A distribuição dos primos segue padrões estudados pela teoria analítica dos números, mas prever o próximo primo exato a partir do anterior continua sendo um problema aberto em certos aspectos.
Como implementar de forma funcional
Se você precisa de primos em um projeto real, o caminho mais direto é usar uma biblioteca existente. Em Python, sympy.primerange ou sieve implementations em Cython rodando em C puro são ordens de magnitude mais rápidos que qualquer coisa feita manualmente em Python puro. Um crivo simples em Python gera todos os primos até 1 milhão em cerca de 0,3 segundos. A mesma lógica em C via Cython ou NumPy com bitarray opera em torno de 0,005 segundos para o mesmo limite. Para gerar primos maiores que 10 milhões e testar primalidade de números específicos, Miller-Rabin com as bases [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37] é suficiente para cobrir todos os números menores que 2^64 com zero falsos positivos conhecidos. Isso significa que você não precisa de um teste adicional para a vasta maioria das aplicações práticas.
A parte mais custosa que as pessoas subestimam é a leitura e escrita de grandes listas de primos. Gerar os primos em si é rápido, mas salvar milhões deles em disco e depois reler para processamento pode levar mais tempo do que o cálculo em si. Armazenar como binário compactado em vez de texto reduz o tempo de I/O em cerca de 70 a 80 por cento no meu caso, quando processei listas de centenas de milhões de primos repetidamente.
