From bfe7a2e6d7e51b3973a169e592c7f507a7d96c2c Mon Sep 17 00:00:00 2001
From: Federico Igne <git@federicoigne.com>
Date: Tue, 29 Dec 2020 09:27:22 +0000
Subject: [rust] Sieve

---
 rust/sieve/src/lib.rs | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)
 create mode 100644 rust/sieve/src/lib.rs

(limited to 'rust/sieve/src')

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..]);
+    }
+}
-- 
cgit v1.2.3