 # Optimizing code: Use a Filter as a Range

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?

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

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.

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