Questăo 4 - Faça um programa que receba 30 números naturais. Seu programa deve exibir:
O menor número primo digitado.
O menor número primo digitado.
Passo 1
O enunciado pede: receber exatamente 30 números naturais (ou seja, 30 entradas) e exibir o menor número primo digitado.
Informações dadas e condições importantes:
Informações dadas e condições importantes:
- Devemos ler
números naturais. - Devemos identificar quais desses números são primos.
- Devemos imprimir o menor dentre os primos lidos.
- O enunciado não diz o que fazer se nenhum primo for digitado — então o programa precisa tratar esse caso e exibir uma mensagem clara (por exemplo: “Nenhum número primo foi digitado”).
Passo 2
O que é um número primo?
Um número inteiro é primo quando
e suas únicas divisores positivos são
e
(ou seja, ele não é divisível por nenhum inteiro entre
e
). Observe que
não é primo. Exemplos:
são primos;
não são.
Um número inteiro
Passo 3
Qual método usar para testar primalidade aqui? (escolha e justificativa)
Para entradas simples e somente números, o método mais direto e suficiente é a divisão por tentativa (trial division), testando se algum inteiro divisor menor ou igual à raiz quadrada de
divide
. A razão: se
tem um divisor
tal que
, então existe um par de fatores
e
com
; pelo menos um entre
e
é
. Logo, é suficiente checar divisores até
. Isso reduz muito o trabalho comparado a checar todos os números até
.
Para entradas simples e somente
Passo 4
Implementando a função de teste de primalidade passo a passo (explicação didática):
- Se
, então não é primo. (Porque primos começam em .) - Se
, é primo. - Se
é par e , não é primo (divisível por ). - Caso contrário, precisamos testar divisores ímpares
começando em até . Para cada , se divide (isto é, ), então não é primo. Se nenhum divisor for encontrado, é primo.
Por que pular pares depois do
? Porque se
não é divisível por
, testar
é inútil — já sabemos que esses não dividirão (são múltiplos de
). Então testamos apenas ímpares
.
Como implementar o limite
sem ponto flutuante? Faça o laço com condição
. Assim usamos multiplicação inteira, segura e exata.
Passo 5
Algoritmo principal (passo a passo de alto nível):
- Inicialize uma variável que guardará o menor primo encontrado, por exemplo
nenhum/sentença (em código: None). - Repita
vezes: - Leia um número
. - Teste se
é primo usando a função de teste descrita. - Se
for primo e ( ainda não definido ou ), atualize .
- Leia um número
- Após ler os
números, se ainda não foi definido, imprima uma mensagem indicando que não houve primos; caso contrário, imprima .
Essa estratégia mantém apenas um valor mínimo em memória e testa primalidade de cada entrada na hora.
Passo 6
Exemplo manual pequeno para fixar (simule um trecho de execução):
Suponha que as primeiras entradas sejam:
Suponha que as primeiras entradas sejam:
- Começa com
nenhum. -
→ não primo → nada muda. -
→ não primo ( divide) → nada muda. -
→ não primo ( divide) → nada muda. -
→ primo → . -
→ primo e → .
A partir daí, nenhum primo menor queexiste, então continuará .
Passo 7
Casos especiais e dicas para a prova:
- Lembre-se:
e não são primos. Trate-os como não primos. - Se o enunciado exigir uma saída em formato específico quando não houver primos, siga-o; caso contrário, uma mensagem como “Nenhum número primo foi digitado” é aceitável.
- Complexidade: cada teste de primalidade custa até
divisões; com apenas números isso é rapidamente executável sem otimizações extras. - Sempre que possível, escreva a função de primalidade separada para evitar repetir código na prova.
Passo 8
Código (implementação prática em Python) — este programa lê
entradas, determina o menor primo e o imprime, ou imprime uma mensagem se não houver primos.
Resposta
def is_prime(n):
# Teste simples de primalidade por tentativa até a raiz quadrada
if n < 2:
return False
if n == 2:
return True
if n % 2 == 0:
return False
i = 3
while i * i <= n:
if n % i == 0:
return False
i += 2
return True
min_primo = None
for _ in range(30):
# Leia um número natural (supondo entrada correta)
n = int(input())
if is_prime(n):
if (min_primo is None) or (n < min_primo):
min_primo = n
if min_primo is None:
print("Nenhum número primo foi digitado")
else:
print(min_primo)