CRIBA DE ERATÓSTENES


La Criba de Eratóstenes es un procedimiento para determinar todos los números primos hasta cierto número natural dado. Esto se hace recorriendo una tabla de números usando el siguiente algoritmo:
  • Comenzamos con el número 2, lo marcamos como número primo y tachamos todos los múltiplos de 2 (es decir, tachamos 4, 6, 8, etc.).
  • Continuamos con el siguiente número no tachado en la tabla, es decir, el número 3, lo marcamos como primo y tachamos todos los múltiplos de 3
  • El siguiente número no tachado en la tabla es el 5, resaltamos el número 5 como primo y tachamos todos los múltiplos de 5
  • El siguiente número no tachado en la tabla es el 7, marcamos el número 7 como primo y tachamos todos los múltiplos de 7
  • El proceso continuaría hasta que el siguiente número no marcado sea mayor que la raíz cuadrada del número más grande de la tabla. Por ejemplo, si cogemos los 120 primeros números podriamos parar tras tachar los múltiplos del 7, ya que la ráiz cuadrada de 120 es menor que 11, y el siguiente número sin marcar es el 11.


Animation that visualizes the "Sieve of Eratosthenes" algorithm. Original image at Image:Animation_Sieve_of_Eratosth.gif
Animation that visualizes the "Sieve of Eratosthenes" algorithm. Original image at Image:Animation_Sieve_of_Eratosth.gif


PRACTICA

Si quieres practicar con la Criba de Eratóstenes, puedes hacerlo desde aquí