Um número n é primo caso ele não seja divisível por nenhum out...

Int ehprimo( int numero ) { 
     if (numero %2 ==0 ) { 
           /* é par, não pode ser primo */ 
          return 0
     }
     int retorno = 1;
     for (int i=3 ; i< (numero/3)+1 ; i+=2 ) {
          if (numero % i == 0 ) { 
               return 0
          }
      }
      return 1
} 

Como funciona.
primeiro testamos se o número é divisível por 2, ou seja, resto da divisào por 2 for igual a 0. Dessa forma, agilizamos os testes. Exceto pelo 2, todos os números primos são ímpares.
O for começa com 3 e vai de 2 em 2 buscando uma divisão que dê resto 0.
Se achar alguma divisào que dê resto 0, o número não é primo. Retornamos 0.
Se chegar ao fim do for, significa que não achou divisor algum, retorna 1. O for só precisa ir até mais ou menos um terço do valor do número. Pois se ele já passou pela divisào por 3 ... o maior divisor dele deve ser menor que um terço.             ​