Escreva um algoritmo que leia um número inteiro positivo, devendo atender o que se pede abaixo: (2,0 pts)
a) Calcular o fatorial do número inteiro positivo n : n!=n *(n-1) *(n-2) * \ldots * 1
b) Verificar e imprimir se o resultado do fatorial é primo ou não. Considerando que os números primos são divisíveis somente por 1 e por ele mesmo.

Passo 1

O enunciado pede duas coisas para um algoritmo que lê um número inteiro positivo:
  • (a) Calcular o fatorial de um inteiro positivo n, isto é \,n! = n\cdot(n-1)\cdot(n-2)\cdots 1.
  • (b) Verificar e imprimir se o resultado do fatorial é primo ou não. Lembrando: um número é primo se é divisível apenas por 1 e por ele mesmo.
Informações relevantes que o enunciado dá:
  • Entrada: um número inteiro positivo n (ou seja n\ge 1).
  • Saída: o valor de n! e uma indicação se n! é primo ou não.
O que o algoritmo deve fazer em termos práticos:
  • Ler n.
  • Calcular n!.
  • Testar primalidade de n!.
  • Imprimir n! e a resposta “primo” ou “não primo”.

Passo 2

O que é fatorial e como calcular na prática (explicação didática e passo a passo).
  • Definição: \,n!=n\cdot(n-1)\cdot(n-2)\cdots 2\cdot1. Por convenção, 1!=1.
  • Método prático (iterativo): inicializar uma variável acumuladora f com f:=1. Para cada inteiro k de 2 até n, fazer f := f \cdot k. Ao final, f=n!.
  • Exemplo concreto: para n=5,
    • iniciar f=1,
    • multiplicar por 2: f=2,
    • multiplicar por 3: f=6,
    • multiplicar por 4: f=24,
    • multiplicar por 5: f=120.
      Logo 5!=120.
Observação prática: n! cresce muito rápido. Em implementações reais é preciso usar um tipo de inteiro com precisão arbitrária (big integer) se n for moderadamente grande; caso contrário ocorre overflow. Mas para um exercício teórico ou para n pequeno, o método iterativo acima basta.

Passo 3

O que é testar se um número m é primo e como fazer isso (explicação didática).
  • Definição: m é primo se tiver exatamente dois divisores positivos distintos: 1 e m.
  • Teste elementar (trial division): para m>1, verificar se existe algum inteiro d com 2\le d\le \lfloor\sqrt{m}\rfloor que divida m ( m \bmod d = 0). Se existir, m é composto; se não existir, m é primo.
  • Por que só até \sqrt{m}? Se m=a\cdot b com a\le b, então a\le\sqrt{m}. Portanto qualquer divisor não-trivial aparece até \sqrt{m}.
  • Casos especiais: 1 não é primo. 2 é primo.

Passo 4

Observação muito importante que simplifica (e que deve ser usada em prova): relação entre n e a primalidade de n!.
  • Para n=1: 1!=1 e 1 NÃO é primo.
  • Para n=2: 2!=2 e 2 é primo.
  • Para n\ge 3: n! é sempre composto. Prova simples: para n\ge 3, n! é divisível por 2 (pois o produto contém o fator 2) e além disso n!/2 é um inteiro maior que 1 (pois há pelo menos um outro fator 3 quando n\ge 3), logo n! tem divisor próprio além de 1 e de n! — portanto é composto.
  • Conclusão útil: em vez de testar primalidade do número gigantesco n! com divisão até \sqrt{n!}, pode-se usar a regra direta:
    • se n=2 então n! é primo;
    • caso contrário ( n=1 ou n\ge 3) então n! não é primo.
Essa observação economiza muito tempo e evita problemas com números muito grandes — perfeito para uma prova.

Passo 5

Estratégia do algoritmo levando em conta as observações:
  • Ler n (validar que é inteiro positivo).
  • Calcular n! por multiplicação iterativa usando um tipo que suporte o tamanho (ou por big integer).
  • Decidir primalidade usando a regra curta descrita no Passo 4:
    • se n=2 então marcar como “primo”;
    • senão marcar como “não primo”.
  • Imprimir o fatorial e a indicação.
Também posso mencionar uma alternativa: se quiser checar primalidade de forma geral (sem a observação), aplicar trial division sobre m=n! até \lfloor\sqrt{m}\rfloor. Mas isso é inviável para n moderadamente grande e desnecessário dado o argumento acima.

Passo 6

Complexidade e cuidados práticos:
  • Cálculo do fatorial (iterativo) faz n-1 multiplicações, complexidade O(n) multiplicações (cada multiplicação pode custar mais tempo se usar big integers).
  • A verificação de primalidade com a regra curta é O(1).
  • Se implementada a verificação por trial division no número m=n!, o custo seria proibitivo: teríamos que testar divisores até \sqrt{m} — impraticável.
  • Cuidados: prever tratamento para entrada inválida (por exemplo n\le 0) e usar big integers se for implementar para n grande.

Passo 7

Exemplos de execução rápida (para fixar a ideia):
  • Entrada n=1: calcula 1!=1. Pela regra, 1 não é primo. Saída: 1! = 1; “não primo”.
  • Entrada n=2: calcula 2!=2. Pela regra, primo. Saída: 2! = 2; “primo”.
  • Entrada n=5: calcula 5!=120. Pela regra, n\ge 3 então não é primo. Saída: 5! = 120; “não primo”.

Resposta

Algoritmo (pseudocódigo em português):
Ler n como inteiro\n
Se n \le 0 então\n
\quad Imprimir “Entrada inválida: digite um inteiro positivo”\n
\quad Terminar\n
FimSe\n
// calcular o fatorial\n
f := 1\n
Para k de 2 até n faça\n
\quad f := f \cdot k\n
FimPara\n
// decidir primalidade usando a observação matemática\n
Se n = 2 então\n
\quad imprimir “fatorial =”, f\n
\quad imprimir “primo”\n
Senão\n
\quad imprimir “fatorial =”, f\n
\quad imprimir “não primo”\n
FimSe

Exercícios relacionados