# Rust: Prime numbers

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
}

• This is not the Sieve of Eratosthenes it is just a brute force method of computing primes up to a certain number.
– Dair
Commented Apr 28, 2017 at 0:44
• @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. Commented Apr 28, 2017 at 2:02
• Don't feel too bad; that is a very common mistake to make about the Sieve. Commented Apr 28, 2017 at 2:20
• Related -- The Genuine Sieve of Eratosthenes. (external link) Commented Jun 9, 2017 at 19:24

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
}

• Probably more important than these points is that he didn't actually implement the Sieve of Eratosthenes...
– Dair
Commented Apr 28, 2017 at 0:47