Crie um algoritmo que leia um número N e verifique se ele é primo. O seu programa deve fazer o MíNIMO de interações possíveis.
Passo 1
Beleza, vamos resolver esse exercício juntos! A questão pede para criar um algoritmo que leia um número
e verifique se ele é primo, fazendo o mínimo de iterações possível. O conteúdo que vamos usar aqui é da matemática, mais especificamente sobre números primos, e também um pouquinho de lógica de programação para otimizar nosso algoritmo.
Passo 2
Primeiro, vamos entender o que é um número primo. Um número primo é aquele que tem exatamente dois divisores distintos: 1 e ele mesmo. Por exemplo, o número 5 é primo porque só pode ser dividido por 1 e por 5 sem deixar resto.
Passo 3
Agora, para verificar se um número
é primo, precisamos testar se ele pode ser dividido por algum número além de 1 e ele mesmo. Se encontrarmos algum divisor nesse intervalo, então
não é primo.
Passo 4
Mas como podemos fazer isso de maneira eficiente, ou seja, com o mínimo de iterações possíveis? Ao invés de verificar todos os números de 2 até
, podemos parar na raiz quadrada de
. Isso porque, se
tiver algum divisor maior que a raiz quadrada, ele já terá um correspondente menor que ela.
Passo 5
Então, vamos calcular a raiz quadrada de
usando a fórmula
. Isso nos dá um limite superior para as possíveis divisões que precisamos checar.
Passo 6
Com o limite definido, vamos criar um loop que vai de 2 até
. Em cada passo do loop, vamos verificar se
é divisível pelo número atual. Se encontrarmos algum divisor, sabemos que
não é primo e podemos encerrar o algoritmo.
Passo 7
Se, depois de todas as iterações, nenhum divisor for encontrado, isso significa que
é primo. Assim, nosso algoritmo confirma que o número é primo.
Resposta
O número
é primo se, ao verificar todos os números de 2 até
, nenhum deles divide
sem deixar resto. Caso contrário,
não é primo.
Exemplo de Algoritmo em Pseudocódigo
início
leia N
se N <= 1 então
escreva "Não é primo"
pare
fim se
é_primo ← verdadeiro
limite ← raiz(N)
para i de 2 até limite faça
se N mod i = 0 então
é_primo ← falso
pare
fim se
fim para
se é_primo então
escreva "É primo"
senão
escreva "Não é primo"
fim se
fim
Este algoritmo lê um número
, verifica se ele é primo fazendo o mínimo de iterações necessárias e retorna o resultado.