1La Criba de Eratóstenes
Un método para calcular todos los números primos menores a un cierto entero positivo dado \(N\) es listar todos los números \(n\) tales que \(1 \lt n \lt N\text{.}\) Comience eleminando todos los múltiplos de 2. Después elimine todos los múltiplos de 3. Ahora elimine todos los múltiplos de 5. Note que 4 ya ha sido eliminado. Continúe de esta manera, notando que no es necesario llegar hasta \(N\text{;}\) es suficiente con parar en \(\sqrt{N}\text{.}\) Usando este método, calcule todos los números primos menores a \(N = 250\text{.}\) También podemos usar este método para encontrar todos los enteros que son relativamente primos a un entero \(N\text{.}\) Simplemente elimine los factores primos de \(N\) y todos sus múltiplos. Usando este método, encuentre todos los números que son relativamente primos con \(N= 120\text{.}\) Usando la Criba de Eratóstenes, escriba un programa que calcule todos los primos menores que un entero \(N\text{.}\)