0
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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> {
    let max_multiplier = max / i;
    (2..=max_multiplier).map(move |n| i * n)
}

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.

\$\endgroup\$
  • \$\begingroup\$ Remarkable that you suggest a small change that duplicates the hand process in use since we discovered the pesky things. Big list of numbers with possible 'Xs—wonder if Eratosthenes used sand or wax before scribing it all down? Reasonable code, great suggestion, I'd say well done… \$\endgroup\$ – hsmyers Feb 1 at 20:12
  • \$\begingroup\$ Now that I think about it, I could return the prime table as an iterator instead, the return expression would be mix of map and filter \$\endgroup\$ – Tommaso Thea Cioni Feb 2 at 13:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.