La Criba de Eratóstenes: Implementación Optimizada en Java

Aunque previamente ya he presentado el algoritmo para encontrar números primos mediante el método de división por tentativa, esa implementación es adecuada si necesitas un número exacto N de los primeros primos. Sin embargo, si buscas números primos dentro de un rango determinado (por ejemplo, que no excedan 1,000,000), es preferible utilizar un algoritmo más rápido.

Esta guía se enfoca en la implementación de la Criba de Eratóstenes en Java, una solución mucho más eficiente.

Entendiendo el algoritmo de la Criba de Eratóstenes

El algoritmo de la Criba de Eratóstenes es un método altamente eficiente para encontrar todos los números primos hasta un límite N. Funciona creando una lista de números desde 2 hasta N y eliminando sistemáticamente los múltiplos de cada primo encontrado, comenzando por el 2. Lo que queda sin tachar es la lista de números primos.

Este método lleva el nombre del científico de la antigua Grecia, Eratóstenes de Cirene.

En esencia, se “criba” el conjunto inicial de números enteros. Como resultado, solo permanecerán los números primos.

Implementación inicial de la Criba de Eratóstenes con un array boolean

A continuación, se presenta la implementación de la Criba de Eratóstenes más simple. El método getAllPrimesLessThan() recibirá como entrada el tamaño de la criba, sieveSize, que define el límite superior del rango de búsqueda. Inicialmente, es necesario crear un array de tipo boolean. Este array funcionará como nuestra criba.

Si el valor del array en el índice N es true, el número N es primo. Si es false, no lo es. Al inicio del algoritmo, todos los elementos del array se inicializan a true mediante el método Arrays.fill(). Los elementos en los índices 0 y 1 se establecen inmediatamente en false, ya que ni 0 ni 1 son números primos.

public List<Integer> getAllPrimesLessThan(int sieveSize) {
    var sieve = new boolean[sieveSize];
    Arrays.fill(sieve, true);
    sieve[0] = false;
    sieve[1] = false;

    for (int i = 2; i < sieve.length; i++) {
        if (sieve[i]) {
            for (int j = 2; i * j < sieve.length; j++) {
                sieve[i * j] = false;
            }
        }
    }

    List<Integer> primes = new ArrayList<>();
    for (int i = 2; i < sieve.length; i++) {
        if (sieve[i]) {
            primes.add(i);
        }
    }
    return primes;
}

Este código para números primos en Java se ejecuta aproximadamente 3 veces más rápido que el método de división por tentativa. No obstante, su rendimiento puede ser optimizado.

Primera optimización: Reduciendo las verificaciones

El número de verificaciones puede reducirse significativamente si se evalúan únicamente los números cuyo cuadrado no excede el rango de búsqueda. En efecto, si $$ N * N $$ es mayor que el tamaño de la criba y todos los múltiplos posibles ya han sido descartados, no es necesario continuar las verificaciones más allá de N.

Además, el bucle anidado puede comenzar a marcar múltiplos desde el cuadrado de i (i*i), ya que todos los múltiplos anteriores ya habrán sido descartados por números primos menores.

for (int i = 2; i * i < sieveSize; i++) {
    if (sieve[i]) {
        for (int j = i * i; j < sieveSize; j += i) {
            sieve[j] = false;
        }
    }
}

Esta pequeña optimización acelera el algoritmo significativamente.

Optimización de memoria con BitSet en Java

El punto más vulnerable del algoritmo para números primos en Java es la necesidad de crear un array que abarque todo el rango de números a verificar. En rangos extensos, es posible que no dispongas de memoria suficiente para crear dicho array.

Para solucionar esto, podemos usar la clase BitSet de BitSet representa un vector de bits, donde cada elemento solo necesita un bit de memoria, lo que reduce el consumo de memoria en un factor de 8 en comparación con un array de boolean. Esta es la clave para una Criba de Eratóstenes optimizada.

La implementación correcta con BitSet para números primos en Java requiere atención a dos detalles cruciales:

1. Inicialización: Se debe establecer como true el rango de bits desde 2 hasta sieveSize (exclusivo).
2. Límites de los bucles: Se debe usar siempre sieveSize como límite superior, y nunca sieve.length(), ya que este último método devuelve el tamaño interno del BitSet (una potencia de 2), no el tamaño lógico que solicitaste.

var sieve = new BitSet(sieveSize);
// Inicializamos como true solo el rango de interés: [2, sieveSize)
sieve.set(2, sieveSize, true);

// Bucle exterior: el límite es sieveSize
for (int i = 2; i * i < sieveSize; i++) {
    if (sieve.get(i)) {
        // Bucle interior: el límite también es sieveSize
        for (int j = i * i; j < sieveSize; j += i) {
            sieve.clear(j); // clear() es equivalente a set(j, false)
        }
    }
}

Esta implementación no solo es mucho más eficiente en memoria, sino que también suele ser ligeramente más rápida debido a operaciones a nivel de bit optimizadas.

Código final: La Criba de Eratóstenes optimizada

En consecuencia, la implementación final, correcta y optimizada del algoritmo para la búsqueda de números primos mediante la Criba de Eratóstenes en Java adopta la siguiente forma:

import java.util.ArrayList;
import java.util.BitSet;
import java.util.List;

public List<Integer> getAllPrimesLessThan(int sieveSize) {
    // Casos base: no hay primos menores o iguales a 2.
    if (sieveSize <= 2) {
        return new ArrayList<>();
    }

    // Usamos BitSet para eficiencia de memoria.
    BitSet sieve = new BitSet(sieveSize);

    // Inicializamos todos los números a partir de 2 como potencialmente primos.
    // El rango para set() es [fromInclusive, toExclusive).
    sieve.set(2, sieveSize, true);

    // Iteramos solo hasta la raíz cuadrada del límite.
    // IMPORTANTE: Usar sieveSize como límite, no sieve.length().
    for (int i = 2; i * i < sieveSize; i++) {
        // Si el número es primo (no ha sido marcado como falso)...
        if (sieve.get(i)) {
            // ...marcamos todos sus múltiplos como no primos.
            // Empezamos desde i*i y usamos sieveSize como límite.
            for (int j = i * i; j < sieveSize; j += i) {
                sieve.clear(j); // clear() es más idiomático que set(j, false).
            }
        }
    }

    List<Integer> primes = new ArrayList<>();
    // Recolectamos los resultados.
    // IMPORTANTE: Usar sieveSize como límite final.
    for (int i = 2; i < sieveSize; i++) {
        if (sieve.get(i)) {
            primes.add(i);
        }
    }

    return primes;
}

Optimizaciones aplicadas:

• Verificar únicamente los números cuyo cuadrado no exceda el rango de búsqueda.
• Reemplazar el array booleano por un conjunto de bits (BitSet) para reducir drásticamente el uso de memoria.

¿Cuándo usar la Criba de Eratóstenes?

La “Criba de Eratóstenes” permite encontrar números primos en un rango determinado varias veces más rápido que el algoritmo de división por tentativa y con un uso de memoria muy optimizado si se utiliza BitSet. Requiere conocer con precisión el rango de búsqueda.

En caso de que el rango de búsqueda no se conozca de antemano o si la velocidad no es un factor crítico, el método de división por tentativa sigue siendo una alternativa viable y más simple.

P.D. La redacción de este artículo fue motivada por el usuario Niko Code, quien ofreció una crítica constructiva sobre el algoritmo de división por tentativa en mi post anterior.