Cómo saber si un número es primo

Un número primo es un entero mayor que 1, que sólo es divisible por 1 y por sí mismo. Algo muy sencillo de comprender, pero difícil de dominar. Desde los griegos, hace ya 2300 años, Euclides demostró que hay infinitos números primos y desde entonces ha habido interés en encontrar una fórmula para generarlos y poder así evitar la engorrosa comprobación, mediante criterios de divisibilidad, para determinar si un número dado tiene divisores diferentes a 1 y a él mismo. 

El matemático griego Eratóstenes propuso una forma (no una fórmula) para encontrar los primeros números primos, hasta un número concreto n dado, mediante una ingeniosa criba que se construye en una tabla en la que están todos los números hasta n y se empieza a tachar los múltiplos de 2, luego los múltiplos de 3, los de 5, 7, 11 y así sucesivamente. Los que quedan sin tachar son primos.

Si queremos conocer a todos los primos menores que 100, por ejemplo, esta es la criba de Eratóstenes resultante: 

Pero en este ejemplo el test solo hay que hacerlo hasta los múltiplos de 7 porque en general, para saber si un numero n es primo, basta verificar que ningún primo menor o igual que su raíz cuadrada lo divide. En nuestro ejemplo la raíz cuadrada de 100 es 10 y el mayor primo que es menor o igual que 10 es precisamente 7.

Este criterio se deduce de un teorema, muy fácil de demostrar, que afirma que si un número n no es primo, entonces tiene un divisor primo que es menor o igual que su raíz cuadrada.

Cuando el número es grande, digamos n = 237 532 341 y tenemos la suerte, como en este caso, de comprobar fácilmente que es múltiplo de 3 porque la suma de sus cifras (= 30) lo es, inmediatamente podemos afirmar que este número no es primo. Pero si quisiéramos hacerlo para un número “grande” que sí es primo, digamos n = 237 532 343, basta comprobar entonces que ningún número primo menor que su raíz cuadrada (en este caso menor que 15 412) lo divide, para poder concluir que sí es primo. 

Hoy en día es fácil programar este algoritmo para verificar si un número dado es o no un número primo, pero la limitante está en la computación cuando se trata de números enormes que desbordan la capacidad de las máquinas.

@MantillaIgnacio