Criba de Eratóstenes en Java

Codigos

El tamiz de Eratóstenes es una de las formas más eficientes de encontrar todos los primos menores que n cuando n es menos que 10 millones.

El algoritmo es muy fácil de entender y no implica nada más que contar números del 2 al máximo número dado. ¿No es fácil? Comienza ordenando todos los números naturales (1, 2, 3, …) en orden numérico. Luego una vez que lea un número primo (empiece por el 2), tiene que hacer que todos los demás múltiplos del ese número sean invisibles (es decir, tacharlos) y leer el siguiente número primo (3 por ejemplo) y repetir el proceso. El resultado será tal que todos los números que se lean (o queden sin tachar) serán números primos.

1. Criba de Eratóstenes

Dado un número n, imprima todos los números primos menores o iguales a n. También se da que n es un número pequeño.

Ejemplo:

Entrada: n = 10
Salida: 2 3 5 7
Entrada: n = 20 
Salida: 2 3 5 7 11 13 17 19

A continuación se presenta el algoritmo para encontrar todos los números primos menores o iguales a un entero n por el método de Eratóstenes:

  1. Crea una lista de enteros consecutivos de 2 a n : (2, 3, 4, …, n ).
  2. Inicialmente, deje p igual a 2, el primer número primo.
  3. A partir de p, cuente en incrementos de p y marque cada uno de estos números mayor que p en la lista. Estos números serán 2p, 3p, 4p, etc .; tenga en cuenta que algunos de ellos ya pueden haber sido marcados.
  4. Encuentra el primer número mayor que p en la lista que no está marcada. Si no hubo tal número, deténgase. De lo contrario, deje que p sea igual a este número (que es el siguiente primo), y repita desde el paso 3.
  5. Cuando el algoritmo termina, todos los números en la lista que no están marcados son primos.

2. Explicación del Algoritmo

Explicación con Ejemplo:

Tomemos un ejemplo cuando n = 50. Por lo tanto, necesitamos imprimir todos los números menores o iguales a 50.

  • Creamos una lista de todos los números del 2 al 50.
Construir Criba de Eratostenes 1
Construir Criba de Eratostenes (1)
  • De acuerdo con el algoritmo, marcaremos todos los números que son divisibles por 2.
Construir Criba de Eratostenes 2
Construir Criba de Eratostenes para múltiplos 2
  • Ahora pasamos a nuestro siguiente número sin marcar (3) y marcamos todos los números que son múltiplos de 3.
Criba de Eratostenes múltiplos de 3
Criba de Eratostenes múltiplos de 3
  • Pasamos a nuestro próximo número 5 sin marcar y marcamos todos los múltiplos de 5.
Criba de Eratostenes múltiplos de 5
Criba de Eratostenes para múltiplos de 5
  • Continuamos este proceso (hasta 7, porque raíz de 50 es aproximadamente 7) y nuestra mesa final se verá a continuación:
Criba de Eratostenes múltiplos de 7
Criba de Eratostenes múltiplos de 7

Entonces los números primos son los no marcados:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

3. Implementación del código

A continuación se muestra la implementación del algoritmo anterior. En la siguiente implementación, una matriz boolean arr[] de tamaño n se usa para marcar múltiplos de números primos.

// Programa Java para imprimir todos los primos menores o iguales a n
// usando Criba de Eratóstenes - Sieve of Eratosthenes
class CribaEratostenes {

    void cribadeEratostenes(int n)
    {
        // Crea una matriz booleana "primo[0..n]" e inicializa todas las entradas como true.
        // Un valor en primo[i] será finalmente false si i no es un primo (si no es verdadero).
        boolean primo[] = new boolean[n+1];
        for(int i=0;i<n;i++)
            primo[i] = true;

        for(int p = 2; p*p <=n; p++)
        {
            // Si el primo[p] no cambia, entonces es primo
            if(primo[p] == true)
            {
                // Actualiza todos los múltiplos de p
                for(int i = p*2; i <= n; i += p)
                    primo[i] = false;
            }
        }

        // Imprimie todos los números primos
        for(int i = 2; i <= n; i++)
        {
            if(primo[i] == true)
                System.out.print(i + " ");
        }
    }

    public static void main(String[] args) {
        int n = 30;
        System.out.print("Los siguientes son los números primos ");
        System.out.println("menores o igual que " + n);
        CribaEratostenes g = new CribaEratostenes();
        g.cribadeEratostenes(n);
    }
}

Salida:

Los siguientes son los números primos menores o igual que 30
2 3 5 7 11 13 17 19 23 29

Complejidad de tiempo: O(sqrt(n)loglog(n))

¿Tienes otro código de implementación? Coméntale!

Algoritmos
  • Criba de Eratóstenes
Sending
User Review
5 (2 votes)

Sobre el Autor:

Hey hola! Yo soy Alex Walton y tengo el placer de compartir conocimientos hacía ti sobre el tema de Programación en Java, desde cero, Online y Gratis.

Deja una Respuesta

*

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.