The implementation of Sieve of Eratosthenes.

sieve.rs

use std::collections::HashMap;

fn sieve(max: usize) -> (Vec<usize>, HashMap<usize, usize>) {
    let mut found_primes = vec![];
    let mut found_least_factor = HashMap::with_capacity(max + 1);
    for n in 2..=max {
        let factor = *found_least_factor.entry(n).or_insert_with(|| {
            found_primes.push(n);
            n
        });
        found_primes
            .iter()
            .map(|&prime| (prime, prime * n))
            .take_while(|&(prime, nth_prime)| prime <= factor && nth_prime <= max)
            .for_each(|(prime, nth_prime)| {
                found_least_factor.insert(nth_prime, prime);
            });
    }
    (found_primes, found_least_factor)
}