Crivo de Eratóstenes em Rust

O Crivo de Eratóstenes e um dos algoritmos mais antigos e elegantes da matemática, criado pelo matemático grego Eratóstenes por volta de 240 a.C. Ele encontra todos os números primos ate um limite N de forma extremamente eficiente, eliminando sistematicamente os múltiplos de cada primo encontrado. Sua complexidade de O(n log log n) o torna muito mais rápido que testar a primalidade de cada número individualmente.

Na prática, o crivo e fundamental em criptografia (geração de primos para RSA), teoria dos números, problemas de programação competitiva e qualquer contexto onde se precise de uma lista completa de primos ate um certo limite. Em Rust, a implementação se beneficia do acesso eficiente a arrays e do controle preciso de memória.

Como Funciona

O algoritmo começa assumindo que todos os números de 2 a N são primos. Em seguida, para cada primo p encontrado, marca todos os seus múltiplos (2p, 3p, 4p, …) como compostos. Os números que sobrevivem ao processo são primos.

Crivo de Eratóstenes para N = 30

Estado inicial: todos marcados como primo (P)
 2  3  4  5  6  7  8  9 10 11 12 13 14 15
 P  P  P  P  P  P  P  P  P  P  P  P  P  P

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
 P  P  P  P  P  P  P  P  P  P  P  P  P  P  P

=== p = 2: eliminar múltiplos de 2 (4, 6, 8, 10, ...) ===
 2  3  4  5  6  7  8  9 10 11 12 13 14 15
 P  P  X  P  X  P  X  P  X  P  X  P  X  X

16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
 X  P  X  P  X  P  X  P  X  P  X  P  X  P  X

=== p = 3: eliminar múltiplos de 3 (9, 12, 15, 18, ...) ===
  (começando de p² = 9, pois 6 já foi eliminado por 2)
 2  3  4  5  6  7  8  9 10 11 12 13 14 15
 P  P  X  P  X  P  X  X  X  P  X  P  X  X

=== p = 5: eliminar múltiplos de 5 (25, 30) ===
  (começando de p² = 25)

=== p > sqrt(30) ≈ 5.47 → parar ===

Resultado (números que permanecem P):
 2  3  5  7  11  13  17  19  23  29

Otimização chave: começar de p² (não de 2p)
  - Quando processamos p=5, os múltiplos 10, 15, 20 já foram
    eliminados por 2 e 3. O primeiro múltiplo não eliminado é 5² = 25.

Complexidade

Operação	Tempo	Espaço
Crivo básico	O(n log log n)	O(n)
Crivo otimizado (sem pares)	O(n log log n / 2)	O(n/2)
Crivo segmentado	O(n log log n)	O(sqrt(n))
Verificar se k é primo (pós-crivo)	O(1)	-
Contar primos até N	O(n) após crivo	-

O(n log log n): o fator log log n cresce tão lentamente que para N = 10^9, log log N ≈ 4.5. Na prática, e quase linear.
Espaço O(n): um array booleano de N posições. Para N = 10^9, isso requer ~1 GB com bool ou ~125 MB com bitset.
Crivo segmentado: reduz o espaço para O(sqrt(N)) processando em blocos.

Implementação em Rust

/// Crivo de Eratóstenes básico: retorna um vetor onde `eh_primo[i]` indica
/// se i é primo, para todos i de 0 a n.
fn crivo_eratostenes(n: usize) -> Vec<bool> {
    let mut eh_primo = vec![true; n + 1];
    eh_primo[0] = false;
    if n >= 1 {
        eh_primo[1] = false;
    }

    let mut p = 2;
    while p * p <= n {
        if eh_primo[p] {
            // Marca todos os múltiplos de p como compostos, começando de p²
            let mut multiplo = p * p;
            while multiplo <= n {
                eh_primo[multiplo] = false;
                multiplo += p;
            }
        }
        p += 1;
    }

    eh_primo
}

/// Extrai a lista de primos a partir do vetor booleano do crivo.
fn listar_primos(eh_primo: &[bool]) -> Vec<usize> {
    eh_primo.iter()
        .enumerate()
        .filter(|&(_, &primo)| primo)
        .map(|(i, _)| i)
        .collect()
}

fn main() {
    let n = 100;
    let eh_primo = crivo_eratostenes(n);
    let primos = listar_primos(&eh_primo);

    println!("Primos até {}: {:?}", n, primos);
    println!("Total: {} primos", primos.len());

    // Verificar primalidade em O(1)
    let teste = [17, 18, 19, 20, 97];
    for &num in &teste {
        println!("{} é primo? {}", num, eh_primo[num]);
    }
}

Exemplo de Execução

Primos até 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]
Total: 25 primos
17 é primo? true
18 é primo? false
19 é primo? true
20 é primo? false
97 é primo? true

Trace do crivo para N = 20:

Inicio: [F, F, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T]
                2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20

p=2: elimina 4, 6, 8, 10, 12, 14, 16, 18, 20
     [F, F, T, T, F, T, F, T, F, F, F, T, F, T, F, F, F, T, F, T, F]

p=3: elimina 9, 15  (começando de 3²=9)
     [F, F, T, T, F, T, F, T, F, F, F, T, F, T, F, F, F, T, F, T, F]

p=4: 4² = 16 > 20? Não, mas eh_primo[4]=false, pula

p=5: 5² = 25 > 20, PARA

Primos: 2, 3, 5, 7, 11, 13, 17, 19

Variações e Otimizações

1. Crivo Otimizado (Pular Números Pares)

Como 2 é o único primo par, podemos pular todos os pares e reduzir o espaço pela metade.

/// Crivo otimizado que ignora números pares (exceto 2).
/// Usa metade da memória do crivo padrão.
fn crivo_otimizado(n: usize) -> Vec<usize> {
    if n < 2 {
        return vec![];
    }

    let mut primos = vec![2];

    // Apenas números ímpares: eh_primo[i] representa o número 2*i + 1
    let tamanho = n / 2;
    let mut eh_primo = vec![true; tamanho + 1];

    // i representa o número ímpar 2*i + 1
    let mut i = 1; // número 3
    while (2 * i + 1) * (2 * i + 1) <= n {
        if eh_primo[i] {
            let p = 2 * i + 1;
            // Primeiro múltiplo ímpar de p que é >= p²
            let mut j = (p * p) / 2;
            while j <= tamanho {
                eh_primo[j] = false;
                j += p; // pula de p em p (apenas ímpares)
            }
        }
        i += 1;
    }

    for i in 1..=tamanho {
        if eh_primo[i] && 2 * i + 1 <= n {
            primos.push(2 * i + 1);
        }
    }

    primos
}

fn main() {
    let primos = crivo_otimizado(100);
    println!("Primos até 100: {:?}", primos);
    println!("Total: {}", primos.len());

    // Teste com limite maior
    let primos_grande = crivo_otimizado(1_000_000);
    println!("\nPrimos até 1.000.000: {} primos", primos_grande.len());
    println!("Últimos 5: {:?}", &primos_grande[primos_grande.len()-5..]);
}

2. Crivo Segmentado para Intervalos Grandes

Quando N é muito grande para caber na memória, processamos em blocos de tamanho sqrt(N).

/// Crivo segmentado: encontra primos no intervalo [baixo, alto].
/// Usa apenas O(sqrt(alto)) de memória.
fn crivo_segmentado(baixo: usize, alto: usize) -> Vec<usize> {
    // Passo 1: encontrar primos até sqrt(alto) com crivo simples
    let limite = (alto as f64).sqrt() as usize + 1;
    let mut eh_primo_base = vec![true; limite + 1];
    eh_primo_base[0] = false;
    if limite >= 1 {
        eh_primo_base[1] = false;
    }

    let mut p = 2;
    while p * p <= limite {
        if eh_primo_base[p] {
            let mut m = p * p;
            while m <= limite {
                eh_primo_base[m] = false;
                m += p;
            }
        }
        p += 1;
    }

    let primos_base: Vec<usize> = (2..=limite)
        .filter(|&i| eh_primo_base[i])
        .collect();

    // Passo 2: crivar o segmento [baixo, alto]
    let tamanho = alto - baixo + 1;
    let mut eh_primo_seg = vec![true; tamanho];

    // Marcar 0 e 1 se estiverem no intervalo
    if baixo == 0 && tamanho > 0 {
        eh_primo_seg[0] = false;
    }
    if baixo <= 1 && 1 >= baixo {
        eh_primo_seg[1 - baixo] = false;
    }

    for &primo in &primos_base {
        // Primeiro múltiplo de primo >= baixo
        let inicio = if baixo <= primo * primo {
            primo * primo
        } else {
            // Arredondar baixo para cima até múltiplo de primo
            ((baixo + primo - 1) / primo) * primo
        };

        let mut m = inicio;
        while m <= alto {
            if m != primo {
                eh_primo_seg[m - baixo] = false;
            }
            m += primo;
        }
    }

    (0..tamanho)
        .filter(|&i| eh_primo_seg[i])
        .map(|i| baixo + i)
        .collect()
}

fn main() {
    // Encontrar primos entre 100 e 200
    let primos = crivo_segmentado(100, 200);
    println!("Primos entre 100 e 200: {:?}", primos);
    println!("Total: {}", primos.len());

    // Primos em intervalo grande
    let primos_grande = crivo_segmentado(999_900, 1_000_100);
    println!("\nPrimos entre 999.900 e 1.000.100: {:?}", primos_grande);
}

3. Fatoração Rápida Usando o Crivo

Podemos modificar o crivo para armazenar o menor fator primo de cada número, permitindo fatoração em O(log n).

/// Crivo que armazena o menor primo fator (SPF) de cada número.
/// Permite fatoração em O(log n) após a construção.
fn crivo_menor_fator(n: usize) -> Vec<usize> {
    let mut spf = vec![0usize; n + 1]; // spf[i] = menor primo que divide i

    for i in 2..=n {
        if spf[i] == 0 {
            // i é primo
            spf[i] = i;
            // Marcar múltiplos de i que ainda não têm spf definido
            if i as u64 * i as u64 <= n as u64 {
                let mut j = i * i;
                while j <= n {
                    if spf[j] == 0 {
                        spf[j] = i;
                    }
                    j += i;
                }
            }
        }
    }

    spf
}

/// Fatoração rápida usando o array SPF: O(log n) por fatoração.
fn fatorar(mut n: usize, spf: &[usize]) -> Vec<(usize, u32)> {
    let mut fatores = Vec::new();

    while n > 1 {
        let p = spf[n];
        let mut exp = 0u32;
        while n > 1 && spf[n] == p {
            n /= p;
            exp += 1;
        }
        fatores.push((p, exp));
    }

    fatores
}

fn main() {
    let n = 1000;
    let spf = crivo_menor_fator(n);

    let numeros = [12, 60, 100, 360, 997, 840];
    for &num in &numeros {
        let fatores = fatorar(num, &spf);
        let fmt: Vec<String> = fatores.iter()
            .map(|&(p, e)| if e == 1 { format!("{}", p) } else { format!("{}^{}", p, e) })
            .collect();
        println!("{} = {}", num, fmt.join(" x "));
    }
}

Aplicações Práticas

Criptografia RSA: a geração de chaves RSA requer números primos grandes. O crivo pode pré-filtrar candidatos antes de testes de primalidade mais rigorosos.
Teoria dos números: estudar a distribuição dos primos, conjectura de Goldbach, primos gêmeos.
Hashing: escolher tamanhos de tabela hash que sejam primos melhora a distribuição dos hashes.
Programação competitiva: inúmeros problemas envolvem primos, fatoração, ou funções multiplicativas que dependem do crivo.
Geradores de números aleatórios: algoritmos como Blum-Blum-Shub dependem de propriedades de números primos.
Compressão de dados: a decomposição em fatores primos é usada em alguns esquemas de codificação.

Comparação com Alternativas

Método	Tempo	Espaço	Encontra todos?	Boa para
Crivo de Eratóstenes	O(n log log n)	O(n)	Sim	N até ~10^8
Crivo otimizado (ímpares)	O(n log log n / 2)	O(n/2)	Sim	N até ~10^9
Crivo segmentado	O(n log log n)	O(sqrt(n))	Em intervalo	N muito grande
Teste de divisão	O(sqrt(n)) por número	O(1)	Um por vez	Poucos testes
Miller-Rabin	O(k log^2 n)	O(1)	Um por vez	N enorme
Crivo linear	O(n)	O(n)	Sim	Fatoração rápida

O Crivo de Eratóstenes é a melhor escolha quando se precisa de todos os primos até N. Para testar primalidade de números individuais muito grandes, prefira Miller-Rabin.

Exercícios Práticos

Função totiente de Euler: Modifique o crivo para calcular phi(n) (a função totiente de Euler) para todos os números de 1 a N. Dica: phi(p) = p-1 para primo p, e phi(p^k) = p^k - p^(k-1). Use o crivo para propagar essas informações.
Primos gêmeos: Use o crivo para encontrar todos os pares de primos gêmeos (p, p+2) até 10.000. Quantos existem? Os primos gêmeos se tornam mais raros a medida que N cresce?
Soma de dois primos (Goldbach): Para cada número par N entre 4 e 100, encontre uma representação como soma de dois primos. Exemplo: 10 = 3 + 7. Dica: para cada primo p <= N/2, verifique se N-p também é primo.
Números suaves (smooth numbers): Usando o crivo de menor fator primo, encontre todos os números até 10.000 cujo maior fator primo é <= 7 (chamados 7-smooth numbers). Esses números são importantes em algoritmos de fatoração como o quadratic sieve.

Veja Também

Algoritmo de Euclides (MDC) em Rust — MDC e relações com primalidade
Exponenciação Rápida em Rust — base para testes de primalidade
Vec — Vetores Dinâmicos — armazenamento do array do crivo
Iterator — Iteradores — filtragem e mapeamento dos resultados
Tipos Numéricos — tipos usize, u64 para limites grandes