Optimizing code: Use a Filter as a Range

help
1

I have the following algorithm to calculate the primes from 2 up to a given number:

pub fn primes_up_to(upper_bound: u64) -> Vec<u64> {
    let mut primes: Vec<u64> = vec![];
    let mut nums: Vec<_> = (2..=upper_bound).collect();

    while let Some(&prime) = nums.iter().next() {
        primes.push(prime);
        nums = nums.into_iter().filter(|&x| x % prime != 0).collect();
    }

    primes
}

and I would like to simplify the code in this way:

pub fn primes_up_to(upper_bound: u64) -> Vec<u64> {
    let mut primes: Vec<u64> = vec![];
    let nums = 2..=upper_bound;

    while let Some(prime) = nums.next() {
        primes.push(prime);

        // Rust failed to compile this line
        nums = nums.filter(|&x| x % prime != 0);
    }

    primes
}

Of course the previous code doesn't compile. Rust throws the following error:

nums = nums.filter(|&x| x %prime);
       ^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::ops::RangeInclusive`, found struct `std::iter::Filter`

But, is it possible to fix in some way the previous code so that it can be compiled?

2

Filter is a lazy iterator combinator, so you can't assign that to a range. Instead, just stick to the imperative approach.

pub fn primes_up_to(upper_bound: u64) -> Vec<u64> {
        let mut primes: Vec<u64> = vec![];

        for x in 2..= upper_bound {
            if primes.iter().any(|&prime| x % prime == 0) {
                continue
            }
            
            primes.push(x);
        }

        primes
}
1 Like
3

If you are looking for optimization, you can rather try to implement a better algorithm than trial division (e.g. the Sieve of Eratosthenes or one of the optimizations for memory use listed on the page) instead of trying to optimize a trial division implementation.

4

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.