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 escribe todos los números desde el 2 hasta tu número dado, incluido.
Después, sigue estos pasos:
- Encuentra el siguiente número sin marcar (saltándote 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 descarta los múltiplos de cada primo usando la suma (sumar el primo repetidamente) o la multiplicación (calcular directamente sus múltiplos), en lugar de comprobar si cada número es divisible.
Los tests no comprueban que hayas implementado el algoritmo, solo que hayas dado con los primos correctos.
Ejemplo
Supongamos que buscas 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 está sin marcar, así que es primo.
Marca 4, 6, 8 y 10 como «no primos».
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
El 3 está sin marcar, así que es primo.
Marca 6 y 9 como no primos (marcar el 6 es opcional, ya que ya está marcado).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 4 está marcado como «no primo», así que nos lo saltamos.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 5 está sin marcar, así que es primo.
Marca 10 como no primo (opcional, ya que ya está marcado).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 6 está marcado como «no primo», así que nos lo saltamos.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 7 está sin marcar, así que es primo.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 8 está marcado como «no primo», así que nos lo saltamos.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 9 está marcado como «no primo», así que nos lo saltamos.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
El 10 está marcado como «no primo», así que paramos, pues no quedan más números que comprobar.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
Has examinado todos los números y has visto que 2, 3, 5 y 7 siguen sin marcar, lo que significa que son los primos menores o iguales que 10.
