Se conoce como número primo a cada número natural que sólo puede dividirse por 1 y por sí mismo.
Un número primo es un número entero mayor que cero, que tiene exactamente dos divisores positivos. También podemos definirlo como aquel número entero positivo que no puede expresarse como producto de dos números enteros positivos más pequeños que él, o bien, como producto de dos enteros positivos de más de una forma. Conviene observar que con cualquiera de las dos definiciones el 1 queda excluido del conjunto de los números primos.
Por citar un ejemplo: 3 es un número primo, mientras que 6 no lo es ya que
6 / 2 = 3 y 6 / 3 = 2.
Para referirse a la cualidad de ser primo, se utiliza el término primalidad.
El término primo no significa que sean parientes de alguien. Deriva del latín "primus" que significa primero (protos en griego). El teorema fundamental de la aritmética afirma que todo número entero se expresa de forma única como producto de números primos. Por eso se les considera los "primeros", porque a partir de ellos obtenemos todos los demás números enteros. (El 15 se obtiene multiplicando los primos 3 y 5)
Como el único número primo par es 2, suele citarse como número primo impar a cualquier número primo que sea más grande que éste.
La primalidad resulta muy importante ya que implica que todo número puede factorizarse como producto de números primos. Esta factorización, por otra parte, siempre será única.
Los 25 primeros números primos son 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 y 97, que son todos los primos menores que 100.
En la tabla inferior tenemos todos los primos menores que 1000, que hacen un total de 168 (21×8)
Para saber si un número es primo (divisible sólo por el mismo y por uno), lo dividimos sucesivamente por los primeros números primos: 2, 3, 5, 7, 11, .. ¿Cuándo paramos de dividir?
Si obtenemos división exacta 
no es primo Si el cociente es menor que el divisor .. paramos es primo
Ejemplo: 113
113 no es divisible por 2 (divisor: 2 , cociente: 56.5) 113 no es divisible por 3 (divisor: 3 , cociente: 37’ ..) 113 no es divisible por 5 (divisor: 5 , cociente: 22’ ..) 113 no es divisible por 7 (divisor: 7 , cociente: 16’ ..) 113 no es divisible por 11 (divisor: 11 , cociente: 10’ ..)
Paramos pues el cociente es menor que el divisor 113 es primo
113 es primo
No es una tarea trivial determinar si un número es primo o no. Saber si un número es primo siempre ha atraído fuertemente a los matemáticos y aficionados que han obtenido algunos éxitos parciales; pero nadie ha obtenido aún una fórmula matemática exacta y de tiempo y estructura algorítmica aceptable que resuelva esta pregunta para todos o un conjunto indefinido de números primos.
Si queremos saber si un número es primo, podemos probar de dividir entre 1,2,3,4…. hasta el número, si ninguno de ellos lo divide, el número será primo.
¿Es necesario mirar todos los números primos hasta el número?
Tampoco, si nos fijamos cuando probamos en orden los números primos, los estamos descartando por orden, por lo tanto el siguiente primo a probar multiplicado por los anteriores no podrá obtener el número como resultado, por lo que como mínimo obtendremos el número con el siguiente primo a probar por el mismo, esto significa que la búsqueda termina con el primo que tenga el cuadrado más cercano al número sin superarlo, o lo que es lo mismo:
Para saber si un número es primo basta con probar si el número no es divisible por los primos hasta su raíz cuadrada.
CASO PRÁCTICO
¿Es 149 primo?
La raiz cuadrada de 149 es 12,2… por lo que solo es necesario probar los números primos hasta 12,2..
probamos con 2,3,5,7,11
149 : 2 = 74,5.. (no es divisible por 2)
149 : 3 = 49,6.. (no es divisible por 3)
149 : 5 = 29,8.. (no es divisible por 5)
149 : 7 = 21,2.. (no es divisible por 7)
149 : 11 = 13,5.. (no es divisible por 11)
149 no puede ser dividido por estos primos por tanto 149 es un número primo.
Hay formulas para determinar números primos de cifras pequeñas, pero se hace difícil de manejar cuando las cifras crecen.
En 2002 apareció un test determinista que asegura en un tiempo polinomial si un número es primo o no. Se conoce como el test AKS y es el descubrimiento moderno en números primos más importante que se ha hecho.
Fuente: mimosa.mec ; definicionde.com; Techastico.com; wikiprimes.com.
