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

Crie a função multiplica_matriz(mat1, mat2) que deve retornar o produto de duas matrizes bidimensionais genéricas, sem alterar as matrizes originais. A função deve imprimir uma mensagem de erro e retornar um vetor vazio ([]) caso não for possível realizar o produto das duas matrizes.
Crie a função mat_transposta(matriz). A função deve receber uma matriz genérica bidimensional, de qualquer tamanho (não necessariamente quadrada) e retornar a matriz transposta, sem alterar a matriz original.
Crie um algoritmo de caixa eletrônico que lê a quantidade de dinheiro a ser sacado e imprime a menor quantidade de notas a ser dada ao usuário. A sua máquina de saque eletrônico é carregada com 1.000 (mil) notas de 100, 50, 20, 10, 5 e 1 cada. Imprimir também a quantidade de cada nota a ser dada ao usuário. Lembre-se que você tem uma quantidade finita de cada tipo de nota. O final da leitura é marcado pelo valor 0 que não deve ser calculado.
Exemplo: 98 = uma nota de 50, duas notas de 20, uma nota de 5, e três notas de 1.
Perceba que a cada saque há uma quantidade menor de cada tipo de notas.
Outra situação é quando não é possível sacar o dinheiro com a quantidade de notas existentes. Neste caso, o programa deve cancelar a operação e informar o usuário que não é possível realizar o saque.
Crie um algoritmo que leia um número (com qualquer número de dígitos) em uma base numérica de ordem < 10 e calcule o número correspondente na base decimal. O número da ordem da base (e.g., 2 para binária, 3 para ternária, 8 para octal, etc.) deve também ser informado pelo usuário.