¿Qué es la criba de Eratóstenes?

La criba de Eratóstenes es un algoritmo para enumerar los números primos menores o iguales a un cierto número. El algoritmo es simple y se puede implementar con los siguientes pasos:

1. Crear un arreglo de valores booleanos de tamaño N e inicializar todos los elementos a true.
2. Establecer el 0º y 1º elemento del arreglo a false (porque 0 y 1 no son primos).
3. Si el 2º elemento del arreglo es true, mostrar 2 como número primo.
4. Establecer a false todos los elementos del arreglo que sean múltiplos de 2 mayores o iguales a $2^2$*.
5. Si el 3º elemento del arreglo es true, mostrar 3 como número primo.
6. Establecer a false todos los elementos del arreglo que sean múltiplos de 3 mayores o iguales a $3^2$.
7. Repetir el mismo proceso para el 4º, 5º, …, N-ésimo elemento.

*Se dirigen los elementos a partir del cuadrado para convertirlos a false porque los números más pequeños que el cuadrado ya han sido procesados (su enumeración se ha completado).

Implementación en Rust

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

fn main() {
    let n = 1000;
    let mut is_prime = vec![true; n+1];
    is_prime[0] = false;
    is_prime[1] = false;
    for i in 2..=n {
        if is_prime[i] {
            println!("{}", i);
            let mut j = i * i;
            while j <= n {
                is_prime[j] = false;
                j += i;
            }
        }
    }
}

Una versión un poco más rápida

Realizaremos una implementación ligeramente más rápida considerando los siguientes puntos:

• Inicializar el arreglo a false en lugar de true (esto es más rápido).
• Omitir el proceso de establecer en false los elementos múltiplos de 2, ya que no son primos.
• No es necesario iterar hasta n; si enumeramos los primos hasta la raíz cuadrada de n, podremos enumerar todos los primos menores o iguales a n.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

fn main() {
    let n = 1000;
    let mut is_prime = vec![false; n+1];
    is_prime[2] = true;
    for i in (3..=n).step_by(2) {
        is_prime[i] = true;
    }
    for i in 3..=((n as f64).sqrt() as usize) {
        if is_prime[i] {
            let mut j = i * i;
            while j <= n {
                is_prime[j] = false;
                j += i * 2;
            }
        }
    }
    for i in (2..=n).filter(|&x| is_prime[x]) {
        println!("{}", i);
    }
}

Referencia

• Criba de Eratóstenes