[rust] Sieve

1 files changed, 16 insertions, 0 deletions

diff --git a/rust/sieve/src/lib.rs b/rust/sieve/src/lib.rs
new file mode 100644
index 0000000..307ff83
--- /dev/null
+++ b/rust/sieve/src/lib.rs
@@ -0,0 +1,16 @@
+pub fn primes_up_to(upper_bound: u64) -> Vec<u64> {
+    let mut sieve: Vec<Option<u64>> = (2..=upper_bound).map(Some).collect();
+    primes(&mut sieve);
+    sieve.iter().filter_map(|x| *x).collect()
+}
+
+fn primes(ps: &mut [Option<u64>]) {
+    if let Some(&n) = ps.first() {
+        if let Some(p) = n {
+            (p as usize..ps.len())
+                .step_by(p as usize)
+                .for_each(|x| ps[x] = None)
+        }
+        primes(&mut ps[1..]);
+    }
+}