Skip to content

Instantly share code, notes, and snippets.

@felix-d
Created April 16, 2018 01:44
Show Gist options
  • Save felix-d/15456f9919ba622453728b71b0e1818b to your computer and use it in GitHub Desktop.
Save felix-d/15456f9919ba622453728b71b0e1818b to your computer and use it in GitHub Desktop.
Sieve of Erathostene in Rust
extern crate num_iter;
use num_iter::range_step;
pub fn sieve(n: u64) -> Vec<u64> {
let mut prime_identifers: Vec<bool> = vec![true; n as usize + 1];
let primes: Vec<u64> = vec![];
for i in 2..(n as f64).sqrt() as usize + 1 {
if *prime_identifers.get(i).unwrap() {
for j in range_step(i.pow(2), n as usize + 1, i) {
prime_identifers[j] = false;
}
}
}
prime_identifers.iter().skip(2).enumerate().fold(
primes,
|mut primes: Vec<u64>, (i, identifier)| {
if *identifier {
primes.push(i as u64 + 2);
}
primes
},
)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment