Skip to content

Instantly share code, notes, and snippets.

@rjvdw
Last active Dec 30, 2021
Embed
What would you like to do?
Computes all primes up to a certain number.
use std::env;
fn main() {
let n = env::args()
.nth(1)
.expect("missing required argument")
.parse()
.expect("expected a valid number");
let primes = sieve(n);
println!("Found {} primes up to {}.", primes.len(), n);
println!("{:?}", primes);
}
fn sieve(n: usize) -> Vec<usize> {
let mut primes = vec![2];
let upper = n / 2 - 1;
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
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_sieve_finds_all_primes_up_to_60() {
assert_eq!(
sieve(60),
vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59],
);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment