la criba de Eratóstenes

CRIBA DE ERATÓSTENES

Eratóstenes fue uno de esos genios de la antigua Grecia que cultivó todas las ramas del saber. Es famoso por haber medido la circunferencia de la Tierra en el siglo III a.C. También ideó un método para encontrar números primos conocido como la criba de Eratóstenes.

Un número natural se considera primo si tiene solo dos divisores distintos: el 1 y el propio número. Los números con más de dos divisores distintos son números compuestos. La criba de Eratóstenes permite encontrar rápidamente todos los primos hasta un cierto número. Se basa en eliminar de la lista de números todos los que sean compuestos. Una vez acabado el proceso, los números que queden sin descartar serán primos.  Vamos a hallar los números primos hasta el 100:

El 1 no aparece porque no se considera primo, al no cumplir con el requisito de tener dos divisores distintos.

criba-de-eratostenes-tabla

Empezamos seleccionando el 2, que es el primer número primo. A continuación vamos contando de 2 en 2 y tachando 4, 6, 8, 10, etc. Es decir, eliminamos los múltiplos de 2.

Seleccionamos el siguiente número primo, el 3. Contamos de 3 en 3, (6, 9, 12, 15…) y vamos tachando los números que no estén ya tachados. Es decir, iremos eliminando los múltiplos de 3 que queden por tachar.

El siguiente número primo sería el 5. Contaremos de 5 en 5, (los múltiplos de 5) e iremos tachando.

Ahora hacemos lo mismo con el 7. Contamos de 7 en 7 (múltiplos de 7) y tachamos.

Ya hemos terminado la criba, todos los números que quedan son primos. Veamos por qué:

El siguiente número sería el 11, si tratásemos de eliminar todos sus múltiplos veríamos que ya están todos tachados (22, 33, 44, 55, 66, 77, 88 y 99) porque también son múltiplos de otros primos más pequeños que 11:

  • 22= 2×11
  • 33= 3×11
  • 44= 2×22
  • 55= 5×11
  • 66= 2×33
  • 77= 7×11
  • 88= 2×44
  • 99= 3×33

Esto ocurrirá siempre que el cuadrado del número que queramos investigar sea mayor que el último número de la lista. En este caso 112 es 121, que es mayor que 100.  Por ejemplo, si el último número fuera el 500 el proceso acabaría cuando llegáramos al 23 porque 232 es 529 y por tanto mayor que 500.

Así que, los números primos del 1 al 100 serán:

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.