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
:
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.
a) Calcular o fatorial do número inteiro positivo
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
, isto é . - (b) Verificar e imprimir se o resultado do fatorial é primo ou não. Lembrando: um número é primo se é divisível apenas por
e por ele mesmo.
Informações relevantes que o enunciado dá:
- Entrada: um número inteiro positivo
(ou seja ). - Saída: o valor de
e uma indicação se é primo ou não.
O que o algoritmo deve fazer em termos práticos:
- Ler
. - Calcular
. - Testar primalidade de
. - Imprimir
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:
. Por convenção, . - Método prático (iterativo): inicializar uma variável acumuladora
com . Para cada inteiro de até , fazer . Ao final, . - Exemplo concreto: para
, - iniciar
, - multiplicar por
: , - multiplicar por
: , - multiplicar por
: , - multiplicar por
: .
Logo.
- iniciar
Observação prática:
cresce muito rápido. Em implementações reais é preciso usar um tipo de inteiro com precisão arbitrária (big integer) se
for moderadamente grande; caso contrário ocorre overflow. Mas para um exercício teórico ou para
pequeno, o método iterativo acima basta.
Passo 3
O que é testar se um número
é primo e como fazer isso (explicação didática).
- Definição:
é primo se tiver exatamente dois divisores positivos distintos: e . - Teste elementar (trial division): para
, verificar se existe algum inteiro com que divida ( ). Se existir, é composto; se não existir, é primo. - Por que só até
? Se com , então . Portanto qualquer divisor não-trivial aparece até . - Casos especiais:
não é primo. é primo.
Passo 4
Observação muito importante que simplifica (e que deve ser usada em prova): relação entre
e a primalidade de
.
- Para
: e NÃO é primo. - Para
: e é primo. - Para
: é sempre composto. Prova simples: para , é divisível por (pois o produto contém o fator ) e além disso é um inteiro maior que (pois há pelo menos um outro fator quando ), logo tem divisor próprio além de e de — portanto é composto. - Conclusão útil: em vez de testar primalidade do número gigantesco
com divisão até , pode-se usar a regra direta: - se
então é primo; - caso contrário (
ou ) então não é primo.
- se
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
(validar que é inteiro positivo). - Calcular
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
então marcar como “primo”; - senão marcar como “não primo”.
- se
- 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
até
. Mas isso é inviável para
moderadamente grande e desnecessário dado o argumento acima.
Passo 6
Complexidade e cuidados práticos:
- Cálculo do fatorial (iterativo) faz
multiplicações, complexidade multiplicações (cada multiplicação pode custar mais tempo se usar big integers). - A verificação de primalidade com a regra curta é
. - Se implementada a verificação por trial division no número
, o custo seria proibitivo: teríamos que testar divisores até — impraticável. - Cuidados: prever tratamento para entrada inválida (por exemplo
) e usar big integers se for implementar para grande.
Passo 7
Exemplos de execução rápida (para fixar a ideia):
- Entrada
: calcula . Pela regra, não é primo. Saída: = 1; “não primo”. - Entrada
: calcula . Pela regra, primo. Saída: = 2; “primo”. - Entrada
: calcula . Pela regra, então não é primo. Saída: = 120; “não primo”.
Resposta
Algoritmo (pseudocódigo em português):
Ler
como inteiro\n
Se então\n
\quad Imprimir “Entrada inválida: digite um inteiro positivo”\n
\quad Terminar\n
FimSe\n
// calcular o fatorial\n
\n
Para de
até
faça\n
\quad \n
FimPara\n
// decidir primalidade usando a observação matemática\n
Se então\n
\quad imprimir “fatorial =”, \n
\quad imprimir “primo”\n
Senão\n
\quad imprimir “fatorial =”, \n
\quad imprimir “não primo”\n
FimSe
Se
\quad Imprimir “Entrada inválida: digite um inteiro positivo”\n
\quad Terminar\n
FimSe\n
// calcular o fatorial\n
Para
\quad
FimPara\n
// decidir primalidade usando a observação matemática\n
Se
\quad imprimir “fatorial =”,
\quad imprimir “primo”\n
Senão\n
\quad imprimir “fatorial =”,
\quad imprimir “não primo”\n
FimSe