Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Computes all primes up to a certain number.
extern crate time;
fn main() {
let nano = 1_000_000_000.0;
let upto = 1_000_000_000;
let start = time::precise_time_ns();
let primes = sieve(upto);
let end = time::precise_time_ns();
println!("found {:?} primes up to {} (in {} seconds).",
primes.len(), upto,
(end - start) as f64 / nano);
}
fn sieve(n: usize) -> Vec<usize> {
let mut primes = vec![2];
let upper = n / 2;
let mut non_primes = vec![false; upper];
let mut i = 0;
while i < upper {
if !non_primes[i] {
let p = 2 * i + 3;
primes.push(p);
let mut j = (p * p - 3) / 2;
while j < upper {
non_primes[j] = true;
j += p;
}
}
i += 1;
}
primes
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment