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 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 escribe todos los números desde el 2 hasta tu número dado, incluido.
Luego, sigue estos pasos:
- Encuentra el siguiente número sin marcar (saltando los números marcados).
Ese es un número primo.
- Marca todos los múltiplos de ese número primo como no primos.
Repite los pasos hasta que hayas recorrido todos los números.
Al final, todos los números sin marcar son primos.
La criba de Eratóstenes tacha los múltiplos de cada primo usando la suma (sumando el primo repetidamente) o la multiplicación (calculando directamente sus múltiplos), en lugar de comprobar la divisibilidad de cada número.
Las pruebas no verifican que hayas implementado el algoritmo, solo que hayas obtenido los primos correctos.
Ejemplo
Supongamos que estás buscando los primos menores o iguales que 10.
-
Escribe 2, 3, 4, 5, 6, 7, 8, 9, 10, dejándolos todos sin marcar.
2 3 4 5 6 7 8 9 10
-
El 2 no está marcado, así que es primo.
Marca 4, 6, 8 y 10 como «no primo».
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
El 3 no está marcado, así que es primo.
Marca 6 y 9 como no primos (marcar el 6 es opcional, ya que ya estaba marcado).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 4 está marcado como «no primo», así que lo saltamos.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 5 no está marcado, así que es primo.
Marca 10 como no primo (opcional, ya que ya estaba marcado).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 6 está marcado como «no primo», así que lo saltamos.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 7 no está marcado, así que es primo.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 8 está marcado como «no primo», así que lo saltamos.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 9 está marcado como «no primo», así que lo saltamos.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 10 está marcado como «no primo», así que nos detenemos, ya que no quedan más números que revisar.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
Ya examinaste 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.
