Programa para determinar se um número é primo em C
Como determinar se um número é primo em C
Olá pessoal!
Seguindo com nossa série de códigos de exemplo para estudo da linguagem C, vamos ver um pequeno programa que permite descobrir se um número dado é primo ou não.
Como sabemos, um número é primo se ele for divisível (divisão inteira) apenas por si mesmo e por 1. Por exemplo:
- O número 17 é primo, pois só é divisível por 17 (ele próprio) e por 1.
- Já o número 18 não é primo, pois além de ser divisível por si mesmo e por 1, também é divisível por outros números, como 2, 3, 6 e 9.
Então, para determinarmos se um dado número é primo, precisamos verificar sua divisibilidade inteira. Para isso, podemos realizar divisões sucessivas do número dado por todos os números a partir de 2 até a metade dele próprio, verificando o resto da divisão. Se o resto for 0 em algum momento, significa que houve uma divisão inteira por um valor diferente de 1 e do número em si, e o número não é primo. Caso contrário, se o resto for diferente de 0 em todas as divisões, o número é primo.
A seguir, temos o código em C que implementa essa função:
Código
#include<stdio.h> #include <locale.h> int main() { setlocale(LC_ALL, ""); int num, i, resultado = 0; printf("Digite um número: "); scanf("%d", &num); for (i = 2; i <= num / 2; i++) { if (num % i == 0) { resultado++; break; } } if (resultado == 0) printf("%d é um número primo\n", num); else printf("%d não é um número primo\n", num); return 0; }
Neste programa simples, declaramos três variáveis: num, i e resultado, que serão usadas para receber o número digitado pelo usuário, contador no processo de verificação de número primo, e para receber o resultado do cálculo, respectivamente.
Usamos as instruções #include <locale.h> e setlocale(LC_ALL,” “) para oferecer suporte ao idioma português na aplicação, de modo a exibir corretamente caracteres especiais e acentuados. Mas ela não é essencial para a execução da aplicação.
A figura a seguir mostra a execução do programa, verificando se um número é primo ou não:
É isso aí pessoal!
Até o próximo tutorial!
Recomendado: Arrays em C – Declaração, Inicialização e Atribuição de valores
Qual a logica de ter dividido por 2 na segunda condicao do for
O algoritmo usa divisões sucessivas do número dado por todos os números a partir de 2 até a metade dele próprio (num/2).
O código possui uma falha, ao inserirmos o valor “4”, a sequência de instruções retorna a informação de que o número 4 é primo.
Revi o código e testei novamente, e parece não ter problemas – ao inserir o valor 4 ele retorna “4 não é um número primo”. Por favor, verifique se não digitou algo errado em seus testes.
num / 2
Ótima sacada. Reduz o numero de loops. 🙂
Agora é só pular os divisores pares e fica ainda mais eficiente.
Encontrei um erro, segundo seu código o número 1 é primo, 1 não é primo pois apenas tem um divisor que é ele mesmo.
Você tem razão, o número 1 não é primo. Fica como desafio: alterem o código do programa para indicar essa condição ao executar o programa.
boa tarde! Em primeiro lugar quero dizer que foi uma ótima sacada iniciar o i com 2 (assim deixa a divisao por 1 de fora). Com relação à condição ser i <= num/2 tem um probleminha. Se digitarmos o número 3, o programa não o avalia. se a condição for i < num, mesmo o programa fazendo algumas verificações a mais, o 3 é considerado como primo.
Entendi o programa, e achei boa a resolução, mas estou com um programa que não estou conseguindo achar solução, tenho até sexta para enviar esse programa para faculdade.
O programa é o seguinte, dado um inteiro n, calcule o menor primo maior que n.
Sei que era pra a data estipulada mas vi agora a pouco seu pedido de ajuda. Sou bem iniciante mas tentei e deu algum resultado. Segue o código:
#include
#include
#include
// Variáveis Globais.
int possivelNovoPrimo;
int num;
void main() {
setlocale(LC_ALL, “”);
// Entrada de dado.
printf(“Digite um número: “);
scanf(“%d”, &num);
// Adiciona o valor digitado a variável que carrega um possível novo valor.
possivelNovoPrimo = num;
proxValor();
}
// Adiciona mais um (+ 1) a variável de teste para testar o próximo valor (um possível número primo).
int proxValor() {
possivelNovoPrimo++;
quantosDividores(possivelNovoPrimo);
}
// Verifica o número de divisores da variável de teste.
int quantosDividores(valor) {
int divisores = 0;
for(int c = 2; c <= valor; c++){
(valor % c == 0) ? divisores++: NULL;
}
verificaPrimo(divisores);
}
// Utiliza o número de divisores para verificar se é um número primo, e caso não seja, vai solicitar um novo valor.
int verificaPrimo(numDivisores) {
if(numDivisores == 1) {
printf("\n%d é o menor primo maior que %d \n", possivelNovoPrimo, num);
} else {
proxValor();
}
}
Dessa maneira se resolve o problema de identificar o 1 como primo.
#include
#include
void main() {
setlocale(LC_ALL, “”);
int num, p = 0;
printf(“Digite um número: “);
scanf(“%d”, &num);
for(int c = 2; c <= num; c++){
(num % c == 0) ? p++: NULL;
}
(p == 1) ? printf("%d é um número primo", num): printf("%d não é um número primo", num);
}
Oi, será que você poderia explicar o código e como ele funciona passo a passo? Eu agradeço
Levando em conta que um número é primo se for explicitamente 2,3,5,7 ou se ele for maior que 9 e não for divisível por nenhum dos 4 números citados anteriormente, a função primo() abaixo resolve esse problema:
#include
bool primo(int n) {
return (n == 2 || n == 3 || n == 5 || n == 7 ||
(n > 9 && n % 2 && n % 3 && n % 5 && n % 7));
};
int main() {
int n=1445,n2=2347;
printf(“%d %s um numero primo\n”,n,primo(n)?”eh”:”nao eh”);
printf(“%d %s um numero primo\n”,n2,primo(n2)?”eh”:”nao eh”);
return 0;
};
Sabendo que a lógica para saber se um número é primo, é quando ele é explicitamente um dos 4 números primos fundamentais (2,3,5,7) ou se ele for maior que 9, e não for divisível por nenhum dos 4 números primos fundamentais, a função primo() abaixo resolve o problema:
#include
bool primo(int n) {
return (n == 2 || n == 3 || n == 5 || n == 7 ||
(n > 9 && n % 2 && n % 3 && n % 5 && n % 7));
};
int main() {
int n=1445,n2=2347;
printf(“%d %s um numero primo\n”,n,primo(n)?”eh”:”nao eh”);
printf(“%d %s um numero primo\n”,n2,primo(n2)?”eh”:”nao eh”);
return 0;
};