Skip to content

Instantly share code, notes, and snippets.

@glebm
Last active August 22, 2020 19:24
Show Gist options
  • Save glebm/440bbe2fc95e7abee40eb260ec82f85c to your computer and use it in GitHub Desktop.
Save glebm/440bbe2fc95e7abee40eb260ec82f85c to your computer and use it in GitHub Desktop.
Rust: Erathosthenes prime sieve
fn is_prime(n: usize, primes: &Vec<usize>) -> bool {
for &p in primes {
let q = n / p;
if q < p { return true };
let r = n - q * p;
if r == 0 { return false };
}
panic!("too few primes")
}
fn primes_lt(bound: usize) -> Vec<usize> {
let mut primes: Vec<bool> = (0..bound + 1).map(|num| num == 2 || num & 1 != 0).collect();
let mut num = 3usize;
while num * num <= bound {
let mut j = num * num;
while j <= bound {
primes[j] = false;
j += num;
}
num += 2;
}
primes.into_iter().enumerate().skip(2).filter_map(|(i, p)| if p {Some(i)} else {None}).collect::<Vec<usize>>()
}
@evgeni-nabokov
Copy link

// primes -- an ordered vector of prime numbers.
fn is_prime(n: usize, primes: &Vec) -> bool {
primes.binary_search(&n).is_ok()
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment