Un número primo es un número mayor que 1 que solo puede dividirse por sí mismo y por 1. Esta definición sugiere que, para saber si el número n es primo o no, se efectúe concienzudamente la división euclídea de n entre 2, luego entre 3, y así sucesivamente hasta que una de ellas sea exacta o se haya probado con n − 1. No es realmente rápido, y aún menos fácil de hacer mentalmente… Por suerte, un poco de aritmética permite reducir mucho las operaciones necesarias, hasta el punto de que determinar si n es primo se convierte en un ejercicio que puede hacerse mentalmente para muchos números no demasiado grandes.
El cribado tiene recompensa ------------------
A Eratóstenes, director de la biblioteca de Alejandría y corresponsal de Arquímedes, se le atribuye la paternidad de un procedimiento para hallar todos los números primos menores que un valor N fijado de antemano: se escribe la lista de los números enteros entre 2 y N, se conserva el 2 y se tachan todos sus múltiplos; después se conserva el 3 y se tachan todos sus múltiplos; luego se conserva el 5 —pues el 4 ya ha sido tachado— y se tachan todos sus múltiplos, y así sucesivamente. Al final, solo quedan sin tachar los números primos entre 2 y N.
Para evaluar la eficacia de la criba de Eratóstenes, podemos observar que, si el producto de dos números p y q es igual a n, al menos uno de los dos números, p o q, es menor o igual que n\sqrt{n}: en efecto, si ambos fueran mayores que n\sqrt{n}, el producto pq sería a su vez mayor que n×n=n,\sqrt{n} \times \sqrt{n} = n, mientras que pq = n. De ello se deduce que, en la criba de Eratóstenes, una vez tachados los múltiplos de los números enteros n para todo n≤Nn \le \sqrt{N}, ya no queda nada que tachar: el trabajo ha terminado.
Este método global de cribado no puede aplicarse realmente de cabeza, por supuesto, pero podemos inspirarnos en él para determinar si un número entero dado a es primo o no. En efecto, si a no es primo, puede escribirse como pq y, según la observación anterior, uno de estos dos factores es menor o igual que a.\sqrt{a}. Basta, por tanto, con comprobar si a es divisible por 2, 3, etc., hasta a,\sqrt{a}, lo cual sigue siendo más rápido que llegar hasta a − 1.