Exercício 2(\mathbf{1 , 0}) Encontre todos os números primos entre 100 e 200.

Passo 1

O que o enunciado pede: encontrar todos os números primos entre 100 e 200.
Informações importantes dadas: o intervalo está entre 100 e 200. Vou entender isso como os inteiros n tais que 100 < n < 200 (ou seja, n=101,102,\dots,199).
Definição usada (útil para a prova): um número inteiro p>1 é primo se seus únicos divisores positivos são 1 e p (caso contrário é composto).

Passo 2

Estratégia clara e por que ela funciona: para testar se um inteiro n é primo, não é necessário tentar dividir n por todos os números menores que n. Basta testar divisibilidade por todos os primos até \sqrt{n}. Explico o porquê de forma curta e direta:
\text{Se }n=a\cdot b\text{ com }1<a\le b<n,\text{ então }a\le\sqrt{n}\text{ e }b\ge\sqrt{n}.ã
Portanto, se não existe divisor a com 2\le a\le\lfloor\sqrt{n}\rfloor, então n não tem fatores próprios e é primo. No nosso caso, como n<200 vale \sqrt{n}<\sqrt{200}\approx14{,}14. Logo bastam os primos até 13, isto é: 2,3,5,7,11,13. Vou usar esse conjunto como teste em todos os candidatos.

Passo 3

Primeiras eliminações rápidas (regras fáceis de aplicar):
  • Se n é par (termina em 0,2,4,6,8) então é divisível por 2 e é composto.
  • Se n termina em 0 ou 5 então é divisível por 5 e é composto.
  • Se a soma dos dígitos de n é múltipla de 3 então n é divisível por 3 (regra do 3).
Aplicando essas regras ao intervalo 101,102,\dots,199 eliminam-se imediatamente todos os pares, todas as terminações em 5 e todos os múltiplos de 3. O que resta são os candidatos ímpares que não são múltiplos de 3 nem de 5. Esses candidatos (para os quais ainda precisamos testar 7,11,13) são:
101,\;103,\;107,\;109,\;113,\;119,\;121,\;127,\;131,\;133,\;137,\;139,
143,\;149,\;151,\;157,\;161,\;163,\;167,\;169,\;173,\;179,\;181,\;187,\;191,\;193,\;197,\;199.

Passo 4

Teste pela divisibilidade por 7. Vou verificar os candidatos que podem ser múltiplos de 7:
  • 119=7\cdot17 portanto composto.
  • 133=7\cdot19 portanto composto.
  • 161=7\cdot23 portanto composto.
Removendo esses, os candidatos restantes são:
101,\;103,\;107,\;109,\;113,\;121,\;127,\;131,\;137,\;139,\;143,\;149,\;151,\;157,\;163,\;167,\;169,\;173,\;179,\;181,\;187,\;191,\;193,\;197,\;199.

Passo 5

Teste pela divisibilidade por 11. Regra rápida: um número é múltiplo de 11 se a diferença entre a soma das casas de ordem par e a soma das casas de ordem ímpar é múltipla de 11; mais simples aqui, eu verifico produtos conhecidos:
  • 121=11\cdot11 portanto composto.
  • 143=11\cdot13 portanto composto.
  • 187=11\cdot17 portanto composto.
Removendo esses, ficam:
101,\;103,\;107,\;109,\;113,\;127,\;131,\;137,\;139,\;149,\;151,\;157,\;163,\;167,\;173,\;179,\;181,\;191,\;193,\;197,\;199.

Passo 6

Teste pela divisibilidade por 13. Verifico as possibilidades:
  • 169=13\cdot13 já era candidato antes; é composto.
  • 143 já foi eliminado no passo anterior por 11.
    Não há outros candidatos nessa lista que sejam múltiplos de 13. Assim não sobra nenhum número composto por divisão por 13.
Depois deste teste, os números que sobraram são todos aqueles que não têm divisores em \{2,3,5,7,11,13\}. Pelo argumento do Passo 2, isso basta para garantir primalidade para números menores que 200.

Passo 7

Confirmação final e contagem. Os números que permaneceram após eliminar todos os compostos pelos testes necessários são, portanto, primos entre 100 e 200:
101,\;103,\;107,\;109,\;113,\;127,\;131,\;137,\;139,\;149,\;151,\;157,\;163,\;167,\;173,\;179,\;181,\;191,\;193,\;197,\;199.
21 números nessa lista.

Resposta

\;101,\;103,\;107,\;109,\;113,\;127,\;131,\;137,\;139,\;149,\;151,\;157,\;163,\;167,\;173,\;179,\;181,\;191,\;193,\;197,\;199

Exercícios relacionados