# Computing a prime table in Rust

My objective is computing a table of primes up to n, where n is a natural number passed as an argument to the prime_table function.

Here is src/lib.rs:

#![feature(vec_remove_item)]

// Return a vector containing all the products between i and natural numbers beyond 2.
// The vector only includes products which are not greater than the maximum specified.
fn get_multiples(i: u32, max: u32) -> Vec<u32> {
let mut results = Vec::new();
let max_multiplier = max / i;
for number in 2..=max_multiplier {
results.push(i * number);
}
results
}

// Return a vector containg all the primes up to n.
pub fn prime_table(n: u32) -> Vec<u32> {
let root_of_n = (n as f64).sqrt() as u32;
let mut table: Vec<u32> = (2..=n).collect();
for i in 2..=root_of_n {
if !table.contains(&i) {
continue;
}
for multiple in get_multiples(i, n).iter() {
table.remove_item(&multiple);
}
}

table
}


Something I'd like but I'm not sure is possible would be changing get_multiples to return an iterator of the results vector instead of the vector itself, but I'm not sure how. If there is a way, I suspect it necessitates lifetimes, something I haven't grasped yet

My main concern is avoiding unnecessarily allocating memory.

Returning an iterator is fairly easy with impl. Here's how you can do it. Note that you need to use move with the closure so that it takes ownership of i. Since u32 can be copied, this just copies it instead of taking a reference, which lets you avoid dealing with lifetimes on the return type.
fn get_multiples(i: u32, max: u32) -> impl Iterator<Item = u32> {

As another note, I have a recommendation for improving performance on your sieve. Currently, every time you call remove_item, you have to search all the way through the vector, remove the item, then shift all items after it forward by one. This is awful for performance. Instead, you could have a Vec<bool> and simply flip the value based on index rather than remove it. Then when you're done sieving, you can go through this vector along with indices and create a Vec<u32> to return.