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

Novembro 2016


Definição de número primo


Um número primo é um inteiro natural, que só pode ser dividido por 1 e por ele mesmo.

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 iterações = %d\n", nb, contar); else printf ("%d não é um número primo, número iterações = %d\n", nb,contar); return 0; }

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

  • os divisores pares não serão testados, a pesquisa se limitando aos divisores impares

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

  • 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 iterações = %d\n", nb, contar); else printf ("%d não é um número primo, número iterações = %d\n",nb, contar); return 0; }

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

  • os divisores impares 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 iterações = %d\n", nb, contar); else printf ("%d não é um número primo, número 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 iterações = %d\n", nb, contar); else printf ("%d não é um número primo, número iterações = %d\n", nb, contar); return 0; }



Tradução feita por Lucia Maurity y Nouira

Veja também :
Este documento, intitulado « Verificar se um inteiro é um número primo em C  »a partir de CCM (br.ccm.net) está disponibilizado sob a licença Creative Commons. Você pode copiar, modificar cópias desta página, nas condições estipuladas pela licença, como esta nota aparece claramente.