Tarea de programación Java – Números primos
Una clásica tarea de programación es encontrar todos los números primos menores por debajo de una cantidad introducida por el usuario. El algoritmo más básico consiste en usar una versión digital de la criba de Eratóstenes que es bastante simple de escribir pero puede volverse muy lenta conforme se incrementa el la cantidad que introduce el usuario. El código en este post es básicamente el algoritmo la criba de Eratóstenes con unas cuantas optimizaciones. En mi PC es posible encontrar todos los números primos menores a 10,000,000 relativamente rápido usando este código. Para los números primos menores a 100,000,000 el código se tarda casi un minuto en mi PC. Para números mayores el tiempo se multiplicaría considerablemente.
El código para encontrar los números primos es el siguiente (lo siento, no pude lograr que wordpress formateara el código correctamente):
public static ArrayList<Integer> numerosPrimos(int max) {
ArrayList<Integer> primos = new ArrayList<Integer>();
primos.add(2);
for (int i = 3; i < max; i++) {
boolean es_primo = true;
double limite = Math.ceil(Math.sqrt(i));
for (int j = 0; j < primos.size(); j++) {
if (i % primos.get(j) == 0) {
es_primo = false;
break;
}
if (primos.get(j) > limite) break;
}
if (es_primo) primos.add(i);
}
return primos;
}
He agregado este método a la clase TareasProgramacion en github. Se puede usar este método como en el siguiente ejemplo:
import java.util.*;
import org.monstruosoft.utils.*;
public class Prueba {
public static void main(String args[]) {
Scanner s = new Scanner(System.in);
System.err.print("Escribe el número máximo para la búsqueda de números primos: ");
int max = s.nextInt();
ArrayList primos = TareasProgramacion.numerosPrimos(max);
for (Integer i: primos)
System.out.println(i);
System.out.println("Se encontraron " + primos.size() + " números primos menores a " + max + ".");
}
}
Al ejecutar el programa obtenemos la siguiente salida:
monstruosoft@debian:~/code/monstruosoft/java-utils$ java Prueba Escribe el número máximo para la búsqueda de números primos: 100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 Se encontraron 25 números primos menores a 100.
