Algoritmo para Encontrar Números Primos en Java

Si te has preguntado cómo encontrar números primos en Java, estás en el lugar correcto. Un número primo es un número que es divisible de forma exacta solo por 1 y por sí mismo. Se sabe también que todo número entero mayor que 1 es primo o puede expresarse como un producto de ellos. La serie comienza con 2, 3, 5, 7, y así sucesivamente.

En este artículo, voy a examinar un algoritmo de números primos en Java conocido como el “método de división por tentativa“. Para ello, implementaré en Java un método getFirstPrimes() que devuelva los primeros N números primos.

Para calcular números primos en Java, se puede usar el método de división por tentativa. Este algoritmo consiste en iterar a través de los números impares y, para cada uno, verificar si es divisible por algún primo ya encontrado que sea menor o igual a su raíz cuadrada. Se utiliza una lista para almacenar los primos hallados.

Implementación del Algoritmo: getFirstPrimes

A continuación, presento el números primos en Java código completo. Este método, getFirstPrimes(), está diseñado para generar números primos en Java hasta una cantidad count especificada.

public List<Integer> getFirstPrimes(int count) {
    if (count < 0) {
        throw new IllegalArgumentException("La cantidad de primos solicitada no puede ser negativa.");
    }
    List<Integer> primes = new ArrayList<>();
    if (count > 0) {
        primes.add(2);
    }
    for (var i = 3; primes.size() < count; i += 2) {
        if (isPrime(i, primes)) {
            primes.add(i);
        }
    }
    return primes;
}

Todos los números primos encontrados se almacenarán en una lista ArrayList. Como se puede observar, he incorporado una validación inicial para asegurar que el argumento count no sea negativo, lanzando una IllegalArgumentException si no se cumple, una práctica recomendada para la robustez del código.

A continuación, se comprueba si se ha solicitado al menos un número primo; si es así, se añade inmediatamente el 2. Luego, en el bucle, se empiezan a verificar los números a partir del tres, evaluando únicamente los números impares (incremento de +2), ya que todos los números pares son, por definición, divisibles por 2.

El bucle se ejecuta hasta que nuestra lista resultante contenga exactamente la cantidad de números primos que se ha solicitado. La verificación de la “primalidad” se realiza mediante el método isPrime(), al que se le pasa el número que se está evaluando y la lista de primos que ya hemos acumulado en iteraciones anteriores.

Verificación de Primalidad: El Método isPrime

En esta primera versión del método, se invoca Math.sqrt(), ya que si un número a evaluar se compone de al menos dos factores, ninguno de ellos puede ser mayor que su raíz cuadrada. Posteriormente, se itera sobre los primos ya encontrados para buscar divisores.

private boolean isPrime(int n, List<Integer> primes) {
    double sqrt = Math.sqrt(n);
    for (var i = 0; i < primes.size(); i++) {
        var prime = primes.get(i);
        if (prime > sqrt) {
            return true;
        }
        if (n % prime == 0) {
            return false;
        }
    }
    return true;
}

Optimizando el Cálculo para Evitar Integer Overflow

Pero, ¿podemos hacerlo aún mejor? La respuesta es sí. Se puede realizar una optimización más robusta para eliminar el cálculo de la raíz cuadrada y las operaciones con el tipo double. En lugar de elevar al cuadrado el divisor (lo que podría causar un desbordamiento de entero con números grandes), reorganizamos la comparación matemática a prime > n / prime.

Esta condición es equivalente y previene posibles errores en casos límite.

private boolean isPrime(int n, List<Integer> primes) {
    for (var i = 0; i < primes.size(); i++) {
        var prime = primes.get(i);
        // Usamos división para evitar el desbordamiento de 'prime * prime'
        if (prime > n / prime) {
            return true;
        }
        if (n % prime == 0) {
            return false;
        }
    }
    return true;
}

Rendimiento y Consideraciones Finales

El programa en Java de números primos analizado funciona con bastante rapidez. En un par de segundos, encuentra 500,000 números primos. Con este método, podrías fácilmente obtener los números primos del 1 al 100 en Java o cualquier otra cantidad que necesites.

Las optimizaciones que he aplicado son:

• Se evalúan únicamente los números impares.
• Se intenta dividir solo por los números primos ya encontrados.
• Los divisores solo pueden ser aquellos primos que no excedan la raíz cuadrada del número evaluado.
• Se utiliza una comparación basada en división (prime > n / prime) en lugar de una multiplicación para evitar el riesgo de desbordamiento de enteros.

Este algoritmo es muy adecuado si necesitas exactamente los primeros N números primos. Si buscas todos los números primos dentro de un rango determinado, es mejor utilizar la Criba de Eratóstenes para encontrarlos, ya que su rendimiento será muy superior.

Y si quieres verificar rápidamente tus resultados, puedes usar una calculadora de números primos online para comparar.