1. 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 0, que indica parada.
  • A cada inteiro lido (antes do 0) devemos considerar se ele é primo; ao final (quando o 0 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 0?
Informações importantes fornecidas:
  • Entrada: inteiros (podem ser positivos, zero aparece apenas como sentinela de parada, podem aparecer 1 e números negativos).
  • Condição de parada: aparecer 0.

Passo 2

O que é um número primo? Relembrando a definição de forma bem prática.
  • Dizemos que um inteiro p é primo se ele satisfaz duas condições:
    1. p>1.
    2. Os únicos divisores inteiros positivos de p são 1 e p (isto é, não existe inteiro d com 1<d<p tal que d divide p).
  • Exemplos: 2 é primo (os divisores positivos são 1 e 2). 3 é primo. 4 não é primo porque 2 divide 4. 1 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 1).

Passo 3

Como testar se um inteiro n (com n>1) é primo — a técnica que vamos usar (teste por divisão até \sqrt{n}).
Motivação e ideia:
  • Se n não for primo, então existe um divisor d com 1<d<n.
  • Se d divide n e d> \sqrt{n}, então o outro divisor correspondente n/d é menor que \sqrt{n}. Logo, sempre existe pelo menos um divisor d com 1<d\le \sqrt{n}.
  • Portanto, basta testar se existe algum inteiro d com 2\le d\le \lfloor\sqrt{n}\rfloor que divide n. Se existir, n não é primo; caso contrário, n é primo.
Implementação prática do teste (detalhes que pode usar na prova):
  1. Se n\le 1, então não é primo.
  2. Se n=2, então é primo.
  3. Se n é par e n>2 (isto é, n \bmod 2 = 0), então não é primo.
  4. Caso contrário, testar todos os impares d a partir de 3 até \lfloor\sqrt{n}\rfloor com passo 2: se algum d divide n ( n \bmod d = 0), então n não é primo; se nenhum dividir, n é primo.
Observações úteis:
  • Verificar apenas até \sqrt{n} economiza trabalho.
  • Pular os pares (após tratar 2) reduz cerca de metade dos testes.
  • Em prova, calcular \lfloor\sqrt{n}\rfloor pode ser feito por aproximação ou por testar d^2\le n 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 max\_prime.
    • No início, max\_prime = \text{nenhum} (ou em implementação: max\_prime = \text{None} / max\_prime = -\infty / max\_prime = 0 dependendo do formato de saída desejado). Aqui vou usar a ideia “nenhum”.
  • Repetir:
    1. Ler um inteiro x.
    2. Se x=0 então parar (vai para saída).
    3. Se x>1 testar se x é primo usando o procedimento do Passo 3.
    4. Se x for primo:
      • Se max\_prime é “nenhum” ou x > max\_prime, então atualizar max\_prime := x.
    5. Voltar a ler o próximo inteiro.
  • Ao parar (quando x=0):
    • Se max\_prime é “nenhum”, imprimir “Nenhum primo encontrado”.
    • Caso contrário, imprimir o valor de max\_prime.

Passo 5

Pseudocódigo claro e compacto (pode reproduzir algo assim na prova se for pedido implementar):
Inicialização:
  • max\_prime \leftarrow \text{nenhum}.
Laço:
  • repetir:
    • ler x
    • se x = 0 então sair do laço
    • se x > 1 então
      • se ehPrimo( x) então
        • se max\_prime = \text{nenhum} ou x > max\_prime então
          • max\_prime \leftarrow x
  • fim repetir
Saída:
  • se max\_prime = \text{nenhum} então imprimir “Nenhum primo encontrado”
  • senão imprimir max\_prime
Função ehPrimo( n):
  • se n \le 1 então retornar falso
  • se n = 2 então retornar verdadeiro
  • se n \bmod 2 = 0 então retornar falso
  • para d \leftarrow 3 até \lfloor\sqrt{n}\rfloor passo 2 faça
    • se n \bmod d = 0 então retornar falso
  • 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:
\;8,\;15,\;2,\;3,\;16,\;17,\;-5,\;0.
Executando o algoritmo:
  • Inicialmente max\_prime = \text{nenhum}.
  • 8: 8>1 mas 8 não é primo (divisível por 2), não atualiza.
  • 15: 15>1 e 15 não é primo (divisível por 3), não atualiza.
  • 2: 2 é primo. max\_prime era “nenhum”, atualiza max\_prime=2.
  • 3: 3 é primo. 3>2 então atualiza max\_prime=3.
  • 16: não é primo, ignora.
  • 17: 17 é primo. 17>3 então max\_prime=17.
  • -5: -5\le 1 na definição usada; não é considerado primo, ignora.
  • 0: parar. Saída: imprimir 17.

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: O(\sqrt{n}) divisões para testar um n.
  • Se houver k números lidos e o maior valor testado for m, custo total aproximado O\!\big(\sum \sqrt{n_i}\big) que na pior situação é O(k\sqrt{m}).
  • Em provas, use as otimizações simples:
    • recuse n\le1 imediatamente;
    • trate 2 separadamente;
    • pule pares;
    • ao testar d\le \sqrt{n} em vez de calcular \sqrt{n} explicitamente, compare d^2 \le n (isso evita raiz).
  • 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 1 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 0 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 max\_prime \leftarrow \text{nenhum}.
Repetir:
\quad Ler x.
\quad Se x = 0 então sair do laço.
\quad Se x > 1 e ehPrimo( x) então
\quad\quad Se max\_prime = \text{nenhum} ou x > max\_prime então max\_prime \leftarrow x.
Depois do laço:
\quad Se max\_prime = \text{nenhum} então imprimir “Nenhum primo encontrado” senão imprimir max\_prime.
Função ehPrimo( n):
\quad Se n \le 1 então retornar falso.
\quad Se n = 2 então retornar verdadeiro.
\quad Se n \bmod 2 = 0 então retornar falso.
\quad Para d \leftarrow 3 até \lfloor\sqrt{n}\rfloor passo 2 faça: se n \bmod d = 0 então retornar falso.
\quad Retornar verdadeiro.

Exercícios relacionados