Criba de Eratóstenes
De Wikipedia, la enciclopedia libre
La criba de Eratóstenes es un algoritmo que permite hallar todos los números primos menores que un número natural dado N. Se forma una tabla con todos los números naturales comprendidos entre 2 y N y se van tachando los números que no son primos de la siguiente manera: cuando se encuentra un entero que no ha sido tachado, ese número es declarado primo, y se procede a tachar todos sus múltiplos. El proceso termina cuando el cuadrado del mayor número confirmado como primo es mayor que N.
Determinemos, mediante este procedimiento, la lista de los números primos menores de 20.
Primer paso: Escribamos la lista de los números naturales comprendidos entre 2 y 20.
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
Segundo paso: Marcamos el primer número no rayado ni marcado como número primo.
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
Tercer paso: Tachamos todos los múltiplos del número que acabamos de marcar como primo.
| 2 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 |
Cuarto paso: Si el cuadrado del número recién marcado es inferior a 20, entonces repetimos el segundo paso. Si no, el algoritmo termina, y todos los enteros no tachados son declarados primos.
Como 3² = 9 < 20, volvemos al segundo paso:
| 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 |
En el cuarto paso, el primer número que no ha sido tachado ni marcado es 5. Como su cuadrado es mayor que 20, el algoritmo termina y consideraremos primos todos los números que no han sido tachados.
RESULTADO: Los números primos comprendidos entre 2 y 20 son: 2, 3, 5, 7, 11, 13, 17, 19.
¿Por qué se detiene el algoritmo cuando el cuadrado del último número primo encontrado es mayor que 20?
Sea P el mayor primo encontrado que cumple P² <= N, y se supone la existencia de un número X tal que:
1.- X es compuesto (esto es, existen Y y Z, ambos distintos de 1, tales que X = YZ
2.- P < X < N.
Como X no fue tachado en el proceso, quiere decir que Y y Z no son menores que P. (1)
A su vez, tanto Y como Z deben ser menores que X, ya que X, Y, Z son naturales. (2)
Por (1) y (2), resulta que Y y Z deben estar entre P y X.
Pero como P² es mayor que N, entonces Y x Z es mayor que N.
Por lo tanto, X resulta mayor que N, siendo que fue definido como menor. La conclusión es entonces, que no existe un X que cumpla las condiciones iniciales.
