Desafio Rust

Pipeline de processamento com iterador personalizado e adaptadores

Enunciado

Crie um iterador Primos que gera números primos infinitamente. Em seguida, use uma cadeia de adaptadores para: pegar os primos, filtrar aqueles cujo quadrado é menor que 200, mapear para o quadrado, e coletar os resultados em um Vec<u64>. Imprima o vetor.

Requisitos

  • Implemente a struct Primos com um campo atual (u64) e implemente Iterator.
  • O método next deve retornar o próximo número primo (começando em 2).
  • Use take_while para parar quando o quadrado for >= 200, ou filter para manter apenas quadrados < 200.
  • Colete em Vec<u64> e imprima.

Código inicial

struct Primos {
    atual: u64,
}

impl Iterator for Primos {
    type Item = u64;
    fn next(&mut self) -> Option<Self::Item> {
        // implemente
    }
}

fn main() {
    let primos = Primos { atual: 2 };
    // use adaptadores para obter quadrados de primos < 200
    let resultado: Vec<u64> = primos
        // ...
        .collect();
    println!("{:?}", resultado);
}

Saída esperada

[4, 9, 25, 49, 121, 169]
Ver dica

Para testar primalidade, verifique divisores de 2 até a raiz quadrada. Use take_while com |&p| p * p < 200.

Mostrar solução 
struct Primos {
    atual: u64,
}

impl Iterator for Primos {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let n = self.atual;
            self.atual += 1;
            if n < 2 {
                continue;
            }
            let mut eh_primo = true;
            let mut d = 2;
            while d * d <= n {
                if n % d == 0 {
                    eh_primo = false;
                    break;
                }
                d += 1;
            }
            if eh_primo {
                return Some(n);
            }
        }
    }
}

fn main() {
    let primos = Primos { atual: 2 };
    let resultado: Vec<u64> = primos
        .take_while(|&p| p * p < 200)  // para quando quadrado >= 200
        .map(|p| p * p)                // quadrado do primo
        .collect();
    println!("{:?}", resultado);
}

Passo a passo

  1. A struct Primos tem um campo atual que armazena o próximo número a testar.
  2. No next, usamos loop para avançar até encontrar um primo. Incrementamos self.atual a cada iteração.
  3. Ignoramos números menores que 2 com continue.
  4. Testamos primalidade dividindo por d de 2 até d*d <= n. Se encontrar divisor, marcamos eh_primo = false e saímos do loop interno.
  5. Se for primo, retornamos Some(n). O loop garante que sempre encontraremos um primo eventualmente, então nunca retornamos None (iterador infinito).
  6. No main, criamos o iterador e usamos take_while(|&p| p * p < 200) para parar quando o quadrado do primo for maior ou igual a 200.
  7. .map(|p| p * p) transforma cada primo em seu quadrado.
  8. .collect() coleta em Vec<u64>.

Por que funciona

O iterador Primos é preguiçoso: cada chamada a next calcula o próximo primo sob demanda. take_while cria um novo iterador que para de consumir assim que a condição falha. map transforma os valores, e collect materializa o resultado. A cadeia é eficiente e não gera primos além do necessário.

Erros comuns

  • Loop infinito no next: se a lógica de primalidade estiver errada (ex.: nunca retornar Some), o programa trava. Teste com números pequenos.
  • Esquecer de incrementar self.atual: causaria repetição infinita do mesmo número. Certifique-se de incrementar antes de testar ou no início do loop.
  • Usar filter em vez de take_while: filter continuaria testando primos para sempre, pois o iterador é infinito. take_while é essencial para parar.
  • Overflow em p * p: para primos grandes, p * p pode estourar u64. Use checked_mul ou limite o escopo.

Outra forma de resolver

Usar uma peneira de Eratóstenes para gerar primos mais rapidamente, mas seria mais complexo. Para este exercício, a divisão por tentativa é suficiente. Outra alternativa é usar std::iter::from_fn para criar o iterador sem struct:

let mut atual = 2;
let primos = std::iter::from_fn(move || {
    loop {
        let n = atual;
        atual += 1;
        if (2..).take_while(|d| d * d <= n).all(|d| n % d != 0) {
            return Some(n);
        }
    }
});

É preferível quando o estado é simples e não precisa ser nomeado.

Saída esperada

[4, 9, 25, 49, 121, 169]