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.
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.