Quais São Os Números Primos Compreendidos Entre 30 E 40

Como identificar números primos na prática

Trabalhar com números primos em um intervalo pequeno como 30 a 40 parece simples de primeira, mas tem pegadinhas que passam despercebidas. A primeira coisa que se deve fazer é testar cada número ímpar do intervalo contra os divisores possíveis. Não adianta só olhar se o número é primo olhando pro lado, porque olhos cansados confundem 33 com primo com frequência. O método direto é dividir pelo 2, depois pelo 3, depois pelo 5, e parar quando o divisor for maior que a raiz quadrada do número. Vamos passar por cada número de 30 a 40. O 30 é par, cai fora. O 31 não divide por 2, não divide por 3 (a soma dos dígitos é 4), não divide por 5 e a raiz quadrada de 31 é pouco mais de 5,5, então basta verificar até o 5 mesmo. 31 é primo. O 32 é par, fora. O 33 parece primo mas 33 dividido por 3 dá 11, então não é. O 34 é par. O 35 termina em 5, dividido por 5 dá 7. O 36 é par. O 37 não divide por 2, por 3 (soma dos dígitos é 10), por 5, e a raiz quadrada é cerca de 6,1, então só preciso testar até 5. 37 é primo. O 38 é par. O 39 divide por 3 dando 13. O 40 é par. Os números primos entre 30 e 40 são 31 e 37.

Uma coisa que muita gente não leva em conta é que o teste de divisibilidade por 3 pode ser feito somando os dígitos. Se a soma for divisível por 3, o número também é. Isso vale para qualquer inteiro e economiza divisão longa. No meu caso, trabalhando com algoritmos de criptografia básica em projetos antigos, já perdi horas debugando um gerador de primos porque o código usava uma função de teste de primalidade que não tratava corretamente o caso do 33. O programa simplesmente pulava o teste por 3 quando a soma dos dígitos era igual a 3, o que é um erro lógico grave. A correção foi trivial: usar sempre a divisibilidade direta em vez de atalhos mal implementados. Outro detalhe prático é que números terminados em 1, 3, 7 ou 9 são os únicos candidatos a primos acima de 10. Isso elimina cerca de 60% dos números do intervalo antes mesmo de começar a testar divisores. No caso de 30 a 40, os candidatos seriam 31, 33, 37 e 39. Destes, 33 e 39 caem no teste por 3. Sobram 31 e 37. Funciona rápido e sem margem para erro. Vale mencionar que esse método manual funciona bem para intervalos pequenos. Para intervalos maiores, como números acima de 100.000, o teste trial division fica inviável e aí se parte para o teste de Miller-Rabin ou para crivos mais eficientes. O intervalo de 30 a 40 não pede tanta complexidade, mas é bom saber onde essa abordagem para de funcionar antes de tentar aplicá-la em situações maiores.