Exercicios Sobre Números Primos

O que são números primos e como resolver os exercícios

Número primo é aquele inteiro maior que 1 que só se divide exatamente por 1 e por ele mesmo. Ponto. 2, 3, 5, 7, 11, 13. O 1 não é primo, então já elimina a primeira armadilha que aparece em todo exercício que eu vejo. O 2 é o único primo par, e isso parece óbvio até cair uma questão pedindo para listar todos os primos menores que 20 e todo mundo esquece de listar o 2. A maioria dos exercícios segue um padrão comum: determinar se um número é primo, decompor em fatores primos, ou encontrar primos dentro de um intervalo. A técnica de prova de primalidade por tentativa de divisão (trial division) é o que vai resolver 90% dos exercícios do ensino médio e do primeiro ano de universidade. Você testa a divisão por todos os primos até a raiz quadrada do número em questão. Se nenhum dividir, o número é primo. Simples e eficiente para números abaixo de 10^12, mas perde eficiência rapidamente quando chega em terrenos maiores.

exercicios sobre números primos

Vou colocar alguns exemplos práticos aqui, porque é assim que você aprende de fato. Exemplo 1: Determine se 221 é primo. A raiz quadrada de 221 fica em torno de 14,86. Então você precisa testar os primos 2, 3, 5, 7, 11 e 13. 221 não é divisível por 2 (ímpar), nem por 3 (soma dos dígitos é 5), nem por 5 (não termina em 0 ou 5). Dividindo por 7 dá 31,57... não exato. Por 11 dá 20,09... também não. Mas por 13, aí sim: 13 × 17 = 221. Logo, 221 não é primo. Achei esse tipo de exercício frequentemente em provas e muita gente travava justamente porque não chegava até o 13, achando que bastava ir até o 11 por engano com a raiz.

Exemplo 2: Decomponha 360 em fatores primos. 360 ÷ 2 = 180
180 ÷ 2 = 90
90 ÷ 2 = 45
45 ÷ 3 = 15
15 ÷ 3 = 5
5 ÷ 5 = 1 Então 360 = 2³ × 3² × 5. Se o exercício pedir o número de divisores, você faz (3+1)(2+1)(1+1) = 24 divisores. Se pedir a soma, (2-1)/(2-1) × (3³-1)/(3-1) × (5²-1)/(5-1) = 15 × 13 × 6 = 1170. Isso cai muito.

Exemplo 3: Liste todos os primos entre 1 e 50 usando o Crivo de Eratóstenes. Você escreve os números de 1 a 50. Riscar o 1 (não é primo). Riscar todos os múltiplos de 2 a partir de 4. Riscar todos os múltiplos de 3 a partir de 9. Riscar todos os múltiplos de 5 a partir de 25. Como 7² = 49, você para por aqui. Os que sobraram são os primos: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. O crivo é eficiente para intervalos pequenos, digamos até 10 milhões, mas começa a consumir muita memória acima disso. Eu já tive que lidar com uma questão de um concurso que pedia primos num intervalo de 100 milhões, e o crivo simples simplesmente não cabia na memória disponível na época. A solução foi usar um crivo segmentado, processando blocos de tamanho gerenciável. Não era algo exigido no exercício original, mas mostra onde a técnica padrão quebra.

Um pitfall comum: muitos alunos confundem numeros compostos com numeros que têm muitos divisores. Um número composto tem pelo menos um divisor além de 1 e dele mesmo. O menor composto é 4. O 9 é composto (divisível por 3). O 25 é composto (divisível por 5). E atenção para os quadrados de primos: eles parecem inofensivos, mas são compostos. Isso cai em quase toda prova. Outro detalhe que passa despercebido: a função totipotente de Euler (n) conta quantos inteiros entre 1 e n são coprimos com n. Para um primo p, (p) = p - 1. Para p^k, (p^k) = p^k - p^(k-1). Isso é direto da multiplicatividade da função. Quando o exercício pede de um número composto, você decompõe e aplica. Nada de decorar fórmulas enormes, a lógica é simples. O que eu mais vejo errado em exercícios é a falta de verificação final. O aluno acha que encontrou os fatores, mas não confere se o produto realmente volta ao número original. Sempre confera. Leva 10 segundos e evita erro bobo que custa ponto.