Prime factors generation

[palacaze]

First of all thank you for this great library.
I don't know if this is strictly in the scope of primal, but I often need to generate the list of prime factors of all the numbers in a range, something like the following:

fn prime_factors(n: usize) -> Vec<Vec<(usize,usize)>> {
    let sieve = primal::Sieve::new(n.sqrt()+1);
    (0..n).map(|i| sieve.factor(i).unwrap_or(Vec::new())).collect()
}

This works just fine but is quite a lot slower than it should be. In fact the following naïve approach if 5 times faster:

#![feature(step_by)]

fn prime_factors_naive(n: usize) -> Vec<Vec<(usize,usize)>> {
    let mut f = vec![Vec::new(); n];
    for i in 2..n {
        // if i is prime
        if f[i].is_empty() {
            // add it as prime factor to all the multiples of i
            for k in (i..n).step_by(i) {
                f[k].push((i, 1));
            }

            // now we handle numbers with several i factors
            for p in (0..).scan(i, |a, _| {*a *= i; Some(*a)}) {
                if p > n { break; }
                for k in (p..n).step_by(p) {
                    f[k].last_mut().unwrap().1 += 1;
                }
            }
        }
    }
    f
}

So... I filed this bug but this is only for your information, I am not convinced myself that this piece of code should be in primal. For once the space requirements are incompatible with a range of more than of few tens of millions.