Exercício
Encontre todos os números primos entre 100 e 200.
Passo 1
O que o enunciado pede: encontrar todos os números primos entre
e
.
Informações importantes dadas: o intervalo está entre e
. Vou entender isso como os inteiros
tais que
(ou seja,
).
Definição usada (útil para a prova): um número inteiro é primo se seus únicos divisores positivos são
e
(caso contrário é composto).
Informações importantes dadas: o intervalo está entre
Definição usada (útil para a prova): um número inteiro
Passo 2
Estratégia clara e por que ela funciona: para testar se um inteiro
é primo, não é necessário tentar dividir
por todos os números menores que
. Basta testar divisibilidade por todos os primos até
. Explico o porquê de forma curta e direta:
Portanto, se não existe divisor
com
, então
não tem fatores próprios e é primo. No nosso caso, como
vale
. Logo bastam os primos até
, isto é:
. Vou usar esse conjunto como teste em todos os candidatos.
Passo 3
Primeiras eliminações rápidas (regras fáceis de aplicar):
- Se
é par (termina em ) então é divisível por e é composto. - Se
termina em ou então é divisível por e é composto. - Se a soma dos dígitos de
é múltipla de então é divisível por (regra do ).
Aplicando essas regras ao intervalo
eliminam-se imediatamente todos os pares, todas as terminações em
e todos os múltiplos de
. O que resta são os candidatos ímpares que não são múltiplos de
nem de
. Esses candidatos (para os quais ainda precisamos testar
) são:
Passo 4
Teste pela divisibilidade por
. Vou verificar os candidatos que podem ser múltiplos de
:
-
portanto composto. -
portanto composto. -
portanto composto.
Removendo esses, os candidatos restantes são:
Passo 5
Teste pela divisibilidade por
. Regra rápida: um número é múltiplo de
se a diferença entre a soma das casas de ordem par e a soma das casas de ordem ímpar é múltipla de
; mais simples aqui, eu verifico produtos conhecidos:
-
portanto composto. -
portanto composto. -
portanto composto.
Removendo esses, ficam:
Passo 6
Teste pela divisibilidade por
. Verifico as possibilidades:
-
já era candidato antes; é composto. -
já foi eliminado no passo anterior por .
Não há outros candidatos nessa lista que sejam múltiplos de. Assim não sobra nenhum número composto por divisão por .
Depois deste teste, os números que sobraram são todos aqueles que não têm divisores em
. Pelo argumento do Passo
, isso basta para garantir primalidade para números menores que
.
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
e
:
Há
números nessa lista.