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.

Exercícios relacionados