Skip to content

Instantly share code, notes, and snippets.

@nicolandu
Created July 17, 2024 17:50
Show Gist options
  • Save nicolandu/70047a0816638b8f98574d55bd294f3d to your computer and use it in GitHub Desktop.
Save nicolandu/70047a0816638b8f98574d55bd294f3d to your computer and use it in GitHub Desktop.
Primes in Rust
#[derive(Copy, Clone, Eq, PartialEq, Debug)]
enum Value {
Unmarked,
Marked
}
pub fn primes_up_to(n: usize) -> Vec<usize> {
assert!(n>=2);
let mut sieve = vec![Value::Unmarked; n];
let mut p = 2;
while p <= n {
for i in (p..n).step_by(p).skip(1) {
sieve[i] = Value::Marked;
}
loop {
p+=1;
if p >= n || sieve[p] == Value::Unmarked {
break;
}
}
}
sieve.iter().enumerate().skip(2).filter(|(_, &v)| v==Value::Unmarked).map(|(i,_)|i).collect()
}
fn main(){
dbg!(primes_up_to(100000000));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment