- Ler vários inteiros e determinar maior número primo, parar com zero.
Passo 1
Vou deixar muito claro o que o enunciado pede e o que ele dá.
- O enunciado dá uma sequência de inteiros lida um a um até que apareça o inteiro
, que indica parada. - A cada inteiro lido (antes do
) devemos considerar se ele é primo; ao final (quando o aparece) devemos determinar qual foi o maior número primo entre os valores lidos. - Saída desejada: o maior número primo encontrado na sequência. Se nenhum número primo foi lido, deve-se indicar isso (aqui vou usar a mensagem: “Nenhum primo encontrado”).
Resumo das perguntas:
- Qual é o maior número primo lido antes do
?
Informações importantes fornecidas:
- Entrada: inteiros (podem ser positivos, zero aparece apenas como sentinela de parada, podem aparecer
e números negativos). - Condição de parada: aparecer
.
Passo 2
O que é um número primo? Relembrando a definição de forma bem prática.
- Dizemos que um inteiro
é primo se ele satisfaz duas condições: -
. - Os únicos divisores inteiros positivos de
são e (isto é, não existe inteiro com tal que divide ).
-
- Exemplos:
é primo (os divisores positivos são e ). é primo. não é primo porque divide . não é primo. Números negativos não são considerados primos para este problema (usa-se a definição padrão: primos são inteiros estritamente maiores que ).
Passo 3
Como testar se um inteiro
(com
) é primo — a técnica que vamos usar (teste por divisão até
).
Motivação e ideia:
- Se
não for primo, então existe um divisor com . - Se
divide e , então o outro divisor correspondente é menor que . Logo, sempre existe pelo menos um divisor com . - Portanto, basta testar se existe algum inteiro
com que divide . Se existir, não é primo; caso contrário, é primo.
Implementação prática do teste (detalhes que pode usar na prova):
- Se
, então não é primo. - Se
, então é primo. - Se
é par e (isto é, ), então não é primo. - Caso contrário, testar todos os impares
a partir de até com passo : se algum divide ( ), então não é primo; se nenhum dividir, é primo.
Observações úteis:
- Verificar apenas até
economiza trabalho. - Pular os pares (após tratar
) reduz cerca de metade dos testes. - Em prova, calcular
pode ser feito por aproximação ou por testar em vez de calcular a raiz explicitamente.
Passo 4
Estratégia geral para o problema (algoritmo passo a passo para fazer “na mão” ou programar):
- Inicializar uma variável que guarde o maior primo encontrado até o momento. Chamemos-a de
. - No início,
(ou em implementação: / / dependendo do formato de saída desejado). Aqui vou usar a ideia “nenhum”.
- No início,
- Repetir:
- Ler um inteiro
. - Se
então parar (vai para saída). - Se
testar se é primo usando o procedimento do Passo 3. - Se
for primo: - Se
é “nenhum” ou , então atualizar .
- Se
- Voltar a ler o próximo inteiro.
- Ler um inteiro
- Ao parar (quando
): - Se
é “nenhum”, imprimir “Nenhum primo encontrado”. - Caso contrário, imprimir o valor de
.
- Se
Passo 5
Pseudocódigo claro e compacto (pode reproduzir algo assim na prova se for pedido implementar):
Inicialização:
-
.
Laço:
- repetir:
- ler
- se
então sair do laço - se
então - se ehPrimo(
) então - se
ou então -
- se
- se ehPrimo(
- ler
- fim repetir
Saída:
- se
então imprimir “Nenhum primo encontrado” - senão imprimir
Função ehPrimo(
):
- se
então retornar falso - se
então retornar verdadeiro - se
então retornar falso - para
até passo faça - se
então retornar falso
- se
- retornar verdadeiro
Passo 6
Exemplo manual passo a passo para fixar a ideia — sequência de entrada e execução:
Suponha que os números lidos sejam, nesta ordem:
.
Executando o algoritmo:
- Inicialmente
. - Lê
: mas não é primo (divisível por ), não atualiza. - Lê
: e não é primo (divisível por ), não atualiza. - Lê
: é primo. era “nenhum”, atualiza . - Lê
: é primo. então atualiza . - Lê
: não é primo, ignora. - Lê
: é primo. então . - Lê
: na definição usada; não é considerado primo, ignora. - Lê
: parar. Saída: imprimir .
Passo 7
Complexidade e dicas para prova (o que lembrar se estiver sem calculadora ou com tempo curto):
- Custo do teste de primalidade por divisão simples:
divisões para testar um . - Se houver
números lidos e o maior valor testado for , custo total aproximado que na pior situação é . - Em provas, use as otimizações simples:
- recuse
imediatamente; - trate
separadamente; - pule pares;
- ao testar
em vez de calcular explicitamente, compare (isso evita raiz).
- recuse
- Se a entrada for muito grande ou houver restrições de tempo, existem testes mais avançados (Miller–Rabin) — não são necessários para enunciados básicos.
Passo 8
Observações finais e cuidados que costumam cair na prova:
- Não tratar
como primo é erro clássico. - Números negativos e zero não são primos; zero serve só como sentinela para parar.
- Se a questão pedir para retornar
quando não houver primo, adapte a saída; aqui usei a mensagem “Nenhum primo encontrado” — siga as especificações do exercício/avaliador. - Em implementações, cuide do tipo de dado (inteiro) e de entradas repetidas (não afeta o algoritmo: atualiza só se maior).
Resposta
Pseudocódigo resumido da solução:
Inicializar
.
Repetir:
Ler
.
Se
então sair do laço.
Se
e ehPrimo(
) então
Se
ou
então
.
Depois do laço:
Se
então imprimir “Nenhum primo encontrado” senão imprimir
.
Função ehPrimo(
):
Se
então retornar falso.
Se
então retornar verdadeiro.
Se
então retornar falso.
Para
até
passo
faça: se
então retornar falso.
Retornar verdadeiro.