Números primos e o Crivo de Eratóstenes

Um dos problemas clássicos de programação é elaborar um algoritmo para calcular/verificar números primos. E uma das formas mais simples que se pode encontrar é através do Crivo de Eratóstenes. Em resumo,

Na metemática, o crivo de Eratóstenes é um algoritmo simples e antigo para encontrar todos os números primos até o limite dado. [Wikipedia]

Veja a imagem abaixo e entenda como funciona este algoritmo:

Em resumo, o algoritmo escolhe os números em sequência e vê quais são seus divisores até a raiz quadrada do limite dado. No exemplo da imagem, sendo o limite 120, o divisor máximo que será testado é a raiz de 120 arredondada para baixo (no caso, 10). Para mais informações, veja a página da Wikipedia.

E para fazer o contrário? Ao invés de achar os números primos, quero saber se um determinado número é primo ou não. Seguimos a mesma lógica do crivo, só que ao contrário =D Veja o código abaixo e acompanhe o seu funcionamento:

#include <stdio.h>
#include <math.h>
#include <locale.h>

int main() {
  int num, max, count = 0, i;
  char answer;
  
  setlocale(LC_ALL, "Portuguese");
  
  do {
    printf("\n\nNúmero a ser testado: ");
    scanf("%d", &num);
    getchar();
    
    max = floor(sqrt(num));   // divisor máximo a ser testado é a
                              // raiz quadrada inteira arredondada
                              // pra baixo do menor número inteiro

    for(i = 2; i <= max; i++){
      if((num % i) == 0) { printf("É divisivel por %d\n", i);count++;}
    }
    
    if(count == 0) printf("%d é primo!", num);
    else printf("%d não é primo", num);
    printf("\n\nTestar outro número? S ou N: ");
    answer = getchar();
    count = 0;
  } while(answer == 'S' || answer == 's');
  return 0;
}

Resumindo, o número só será primo se não for encontado nenhum divisor. E os divisores são testados/encontrados à bruta força, ou seja, testando todos os valores até o valor limite (raiz quadrada do número dado).

Abaixo segue a sub-rotina, comentada e pronta para implementação ;) (lembre-se de incluir a biblioteca <math.h>, para as funções floor e sqrt).

int isPrime(int num){  // Crivo de Eratóstenes
  // por Gutierrez PS - http://about.me/gutierrezps
  int max, count = 0, i, resp;

  if(num >= 2) {  // só pode ser primo se maior ou igual a 2
    max = floor(sqrt(num));   // maior divisor será a raiz quadrada arredondada pra baixo

    for(i = 2; i <= max; i++){    // compara todos os divisores
      if((num % i) == 0) count++;   // se for divisível, incrementa count
    }

    if(count == 0) resp = 1;    // se não for encontrado nenhum divisor, é primo
    else resp = 0;
  } else resp = 0;

  return resp;    // retorna 1 se for primo
}