1 files changed, 41 insertions, 0 deletions
diff --git a/segmented_sieve.cc b/segmented_sieve.cc
new file mode 100644
index 0000000..b5974bb
--- /dev/null
+++ b/segmented_sieve.cc
@@ -0,0 +1,41 @@
+#include "sieve.hh"
+#include <cmath>
+#include <cstring>
+
+[[nodiscard]] std::vector<int> segmentedSieve(std::size_t size) {
+  const size_t s = sqrt(size);
+  const auto primes = sieve3(s);
+  std::vector<int> r{primes};
+  std::vector<int> r2;
+
+  size_t l = s;
+  size_t h = l + s;
+  unsigned char *n = (unsigned char *)malloc(s);
+
+  while (l < size) {
+
+    memset(n, false, s);
+
+    for (const auto prime : primes) {
+      // find the first number divisible by prime
+      std::size_t f = (l / prime) * prime;
+      if (f < l)
+        f += prime;
+
+      for (std::size_t i = f; i < h; i += prime)
+        n[i - l] = true;
+    }
+    for (std::size_t i = 0; i < s; ++i)
+      if (n[i] == false)
+        r2.emplace_back(i + l);
+
+    l += s;
+    h += s;
+  }
+
+  free(n);
+
+  r.reserve(r.size() + r2.size());
+  r.insert(r.end(), r2.begin(), r2.end());
+  return r;
+}