Introducción
Compraste una caja grande de piezas de computadora al azar en una venta de garaje.
Empezaste a armar las piezas para construir computadoras personalizadas.
Quieres probar el rendimiento de distintas combinaciones de piezas y decides crear tu propio programa para medir el rendimiento y ver así cómo se comparan tus computadoras.
Eliges el famoso algoritmo «criba de Eratóstenes», un algoritmo antiguo, pero que debería llevar tus computadoras 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 entre 1 y 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 entre 1 y sí mismo, sino también entre 2 y 3.
Para usar la criba de Eratóstenes, primero creas una lista con todos los números entre 2 y el número dado.
Luego repites los siguientes pasos:
- Encuentra el siguiente número sin marcar de tu lista (saltando los números marcados).
Este es un número primo.
- Marca todos los múltiplos de ese número primo como no primos.
Repites estos pasos hasta que hayas recorrido cada número de tu lista.
Al final, todos los números sin marcar son primos.
Las pruebas no comprueban que hayas implementado el algoritmo, solo que hayas obtenido la lista correcta de primos.
Para comprobar que estás implementando la criba correctamente, una buena primera prueba es verificar que no uses 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, y déjalos todos sin marcar.
- El 2 no está marcado, así que es primo.
Marca el 4, el 6, el 8 y el 10 como «no primos».
- El 3 no está marcado, así que es primo.
Marca el 6 y el 9 como no primos (marcar el 6 es opcional, ya que ya está marcado).
- El 4 está marcado como «no primo», así que lo saltamos.
- El 5 no está marcado, así que es primo.
Marca el 10 como no primo (opcional, ya que ya está marcado).
- El 6 está marcado como «no primo», así que lo saltamos.
- El 7 no está marcado, así que 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 hay más números que revisar.
Has examinado todos los números y encontraste que 2, 3, 5 y 7 siguen sin marcar, lo que significa que son los primos menores o iguales que 10.
