Verificar se um número inteiro é um número primo em C

Setembro 2017


Na matemática, um número primo é um número inteiro natural que só pode ser dividido por 1 ou por ele mesmo. Por exemplo, o número 7 é considerado primo pois só é divisível por 1 - como todos os outros números naturais - e por ele mesmo. Já o número 8, por exemplo, não é primo, pois pode ser dividido por 2 e 4, além de 1 e 8.

Dica: com exceção do número 2 (divisível apenas por 1 e 2), todos os outros números primos são ímpares. Isso ocorre pois qualquer número par será divisível por 2, impedindo, portanto, que eles sejam divididos somente por 1 e por eles mesmos.

Algoritmo 1: os divisores entre 2 e N-1 serão testados

Os divisores entre 2 e N-1 serão testados:


/**************************\ 

  • número_primo1.c * \**************************/ /* algoritmo: teste todos os divisores */ #include <stdio.h> int main (void) { int i, nb, contar, teste; teste = contar = 0; printf ("Entre um número inteiro: "); if (scanf ("%d", &nb) != 1) return -1; for (i = 2; i < nb; i++, contar++) if (nb % i == 0) teste = 1; if (!teste) printf ("%d número primo, número de iterações = %d\n", nb, contar); else printf ("%d não é um número primo, número de iterações = %d\n", nb,contar); return 0; }

Algoritmo 2: os divisores pares não serão testados, a pesquisa se limitando aos divisores ímpares

Os divisores pares não serão testados, a pesquisa se limitando aos divisores ímpares:


/**************************\ 

  • número_primo2.c * \**************************/ /* algoritmo: exclua os números pares e * teste todos os divisores */ #include <stdio.h> int main (void) { int i, nb, contar, teste; teste = contar = 0; printf ("Entre um número inteiro:"); if (scanf ("%d", &nb) != 1) return -1; if (nb % 2 == 0) teste = 1; else{ for (i = 3 ; i < nb; i+=2, contar++) if (nb % i == 0) teste = 1; } if (!teste) printf ("%d número primo, número de iterações = %d\n", nb, contar); else printf ("%d não é um número primo, número de iterações = %d\n",nb, contar); return 0; }

Algoritmo 3: os divisores ímpares até a raiz quadrada do N serão testados

Os divisores ímpares até a raiz quadrada do N serão testados:


/**************************\ 

  • número_primo3.c * \**************************/ /* algoritmo: exclua os números pares e * teste todos os divisores até a raiz quadrada */ #include <stdio.h> #include <math.h> int main (void) { int i, nb, contar, teste, limite; teste = contar = 0; printf ("Entre um número inteiro: "); if (scanf ("%d", &nb) != 1) return -1; limite = sqrt(nb) + 1; if (nb % 2 == 0) teste = 1; else{ for (i = 3 ; i < limite; i+=2, contar++) if (nb % i == 0) teste = 1; } if (!teste) printf ("%d número primo, número de iterações = %d\n", nb, contar); else printf ("%d não é um número primo, número de iterações = %d\n",nb, contar); return 0; }

Algoritmo 4: parada do programa quando um divisor é encontrado

Parada do programa quando um divisor é encontrado:


/**************************\ 

  • número_primo4.c * \**************************/ /* algoritmo: exclua os números pares e * teste todos os divisores até a raiz quadrada * e saída do circuito no 1° divisor encontrado */ #include <stdio.h> #include <math.h> int main (void) { int i, nb, contar, teste, limite; teste = contar = 0; printf ("Entre um número inteiro : "); if (scanf ("%d", &nb) != 1) return -1; limite = sqrt(nb) + 1; if (nb % 2 == 0) teste = 1; else{ for (i = 3 ; i < limite && ! teste; i+=2, contar++) if (nb % i == 0) teste = 1; } if (!teste) printf ("%d número primo, número de iterações = %d\n", nb, contar); else printf ("%d não é um número primo, número de iterações = %d\n", nb, contar); return 0; }

Foto: © Pixabay.

Veja também

Artigo original publicado por lami20j. Tradução feita por pintuda. Última modificação: 23 de agosto de 2017 às 10:53 por Pedro.CCM.
Este documento, intitulado 'Verificar se um número inteiro é um número primo em C ', está disponível sob a licença Creative Commons. Você pode copiar e/ou modificar o conteúdo desta página com base nas condições estipuladas pela licença. Não se esqueça de creditar o CCM (br.ccm.net) ao utilizar este artigo.