2
\$\begingroup\$

A first attempt to implement the Sieve of Eratosthenes to find all the prime numbers from 2 up to a given number resulted in this brute force algorithm. A user pointed out, that this is in fact not the Sieve of Eratosthenes, but just a brute force algorithm and should be reviewed as such.

#![feature(inclusive_range_syntax)]

pub fn primes_up_to(limit: u64) -> Vec<u64> {
    let mut vec: Vec<u64> = (2...limit).collect::<Vec<_>>();

    for p in 2...limit {
        vec.retain(|&x| x <= p || x % p != 0);
    }

    vec
}
\$\endgroup\$
  • \$\begingroup\$ This is not the Sieve of Eratosthenes it is just a brute force method of computing primes up to a certain number. \$\endgroup\$ – Dair Apr 28 '17 at 0:44
  • \$\begingroup\$ @Dair, I'm incredible sorry that I've mislead you. I also mislead myself. But thanks to your comment, I realize my foolishness. Even though I was heavenly influenced by reading about the Sieve, this isn't it. I changed the title and hopefully made clear, that this is not what I originally thought it was. Thanks again for pointing this out multiple times. \$\endgroup\$ – snakeandrooster Apr 28 '17 at 2:02
  • \$\begingroup\$ Don't feel too bad; that is a very common mistake to make about the Sieve. \$\endgroup\$ – Shepmaster Apr 28 '17 at 2:20
  • \$\begingroup\$ Related -- The Genuine Sieve of Eratosthenes. (external link) \$\endgroup\$ – CAD97 Jun 9 '17 at 19:24
2
\$\begingroup\$

This seems pretty straight-forward, only minor nits:

  1. You don't need the turbofish on collect; the type declaration on the let is enough of a hint.
  2. That type doesn't need to specify the type of the vector element, it can be inferred.
  3. Really reaching for straws, the p and x variables could be a bit longer, or x % p != 0 could be made into a function with a name, just so that there's no mental overhead in reading the code.
pub fn primes_up_to(limit: u64) -> Vec<u64> {
    let mut vec: Vec<_> = (2...limit).collect();

    for p in 2...limit {
        vec.retain(|&x| x <= p || x % p != 0);
    }

    vec
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Probably more important than these points is that he didn't actually implement the Sieve of Eratosthenes... \$\endgroup\$ – Dair Apr 28 '17 at 0:47

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.