From 57027fd076504b219f3e886e78535191f6abbb66 Mon Sep 17 00:00:00 2001
From: aqua <aqua@iserlohn-fortress.net>
Date: Sat, 18 Mar 2023 07:17:27 +0200
Subject: Initial commit

Sieve of Eratosthenes
- simple implementation and optimized versions
- Segmented sieve with pthreaded version
---
 segmented_sieve.cc | 41 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 41 insertions(+)
 create mode 100644 segmented_sieve.cc

(limited to 'segmented_sieve.cc')

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;
+}
-- 
cgit v1.2.1