Introducción
Compraste una caja grande de piezas de ordenador al azar en una venta de garaje.
Has empezado a montar las piezas para construir ordenadores a medida.
Quieres poner a prueba el rendimiento de distintas combinaciones de piezas y decides crear tu propio programa de benchmarking para ver cómo se comparan tus ordenadores.
Eliges el famoso algoritmo de la «criba de Eratóstenes», un algoritmo antiguo, pero que debería llevar tus ordenadores al límite.
Instrucciones
Tu tarea es crear un programa que implemente el algoritmo de la criba de Eratóstenes para encontrar todos los números primos menores o iguales que un número dado.
Un número primo es un número mayor que 1 que solo es divisible por 1 y por sí mismo.
Por ejemplo, 2, 3, 5, 7, 11 y 13 son números primos.
En cambio, 6 no es un número primo, ya que no solo es divisible por 1 y por sí mismo, sino también por 2 y por 3.
Para usar la criba de Eratóstenes, primero creas un array con todos los números entre el 2 y el número dado.
Después repites los siguientes pasos:
- Busca el siguiente número sin marcar de tu array (saltándote los números marcados).
Ese número es primo.
- Marca todos los múltiplos de ese número primo como no primos.
Repites estos pasos hasta haber recorrido todos los números de tu array.
Al final, todos los números sin marcar son primos.
Los tests no comprueban que hayas implementado el algoritmo, solo que has dado con el array de primos correcto.
Para comprobar que estás implementando la criba correctamente, un buen primer test es verificar que no usas operaciones de división ni de residuo.
Ejemplo
Supongamos que buscas los primos menores o iguales que 10.
- Escribe 2, 3, 4, 5, 6, 7, 8, 9 y 10, dejándolos todos sin marcar.
- El 2 está sin marcar y, por tanto, es primo.
Marca 4, 6, 8 y 10 como «no primo».
- El 3 está sin marcar y, por tanto, es primo.
Marca 6 y 9 como no primos (marcar el 6 es opcional, ya que ya estaba marcado).
- El 4 está marcado como «no primo», así que lo saltamos.
- El 5 está sin marcar y, por tanto, es primo.
Marca el 10 como no primo (opcional, ya que ya estaba marcado).
- El 6 está marcado como «no primo», así que lo saltamos.
- El 7 está sin marcar y, por tanto, es primo.
- El 8 está marcado como «no primo», así que lo saltamos.
- El 9 está marcado como «no primo», así que lo saltamos.
- El 10 está marcado como «no primo», así que paramos, ya que no quedan más números que comprobar.
Has examinado todos los números y has comprobado que 2, 3, 5 y 7 siguen sin marcar, lo que significa que son los primos menores o iguales que 10.
