Muchas personas están buscado determinar si un número es primo, y la mayoría de las web sobre programación tienen incluido un algoritmo para comprobar si un número dado es primo. He aquí  te mostrare 2 formas de comprobar si es un número primo.

Un número es primo si no es un múltiplo exacto de cualquier otro número, excepto si este es si mismo y el número 1, es decir, si no tiene factores excepto sí mismo y 1. Un ejemplo para entenderlo es el siguiente. Supongamos que P es el número para ser probado. Veamos, si en todos los números de N que dividan con P no se haya encontrado el resto, en el caso de que no se encontrara consideramos que P es primo.

Algunos pasos para determinar si es un numero primo

Para empezar podemos utilizar la raíz cuadrada porque no es necesario probar todos los factores posibles, solo se requiere probar los factores que están entre 2 y la raíz cuadrada de p, ya que los factores mayores a la raíz cuadrada de p no son mas que los factores menores a la raíz cuadrada de p, solo que están organizados de forma diferente.

A continuación el algoritmo Estándar escrito en Java para determinar si es primo o no:

int is_prime(int p) {
    for( int n=2; n<=(int) Math.sqrt(p); n++){
         if ( p%n == 0 ){
              return 0; //no es primo
         }
    }
    return 1;//es primo
}

Nota: Este algoritmo contempla al numero 1 como primo al introducir el valor para verificar si es primo(aunque lo verifica como primo sigue correctamente la regla), actualmente el 1 no se considera primo es por eso que a continuación vera otro algoritmo de forma mas optimizada.

Algoritmo escrito en Java que excluye al numero 1 como numero primo, un poco mas optimizado.

Podemos simplificar las cosas mediante la restricción de P con N haciendo que N solo tome los números impares, porque si N es par podría decirse entonces que N es compuesto y no es primo, así que sólo tenemos que tratar divisores impares N.

int is_prime(int p) {
    if (p == 1) return 0; // 1 no es primo
    if (p == 2) return 1; // 2 es primo
    if (p%2 == 0) return 0; // no es primo ningún par, excepto el 2
    for (int n=3; n*n<=p; n+=2) // inicia desde  3, saltando 2 números
         if (p%n == 0) // no hay la necesidad de comprobar los numero pares
              return 0;
    return 1;
}