Initial commitHEADmaster

Sieve of Eratosthenes
- simple implementation and optimized versions
- Segmented sieve with pthreaded version

1 files changed, 58 insertions, 0 deletions

diff --git a/sieve.cc b/sieve.cc
new file mode 100644
index 0000000..4f7c84f
--- /dev/null
+++ b/sieve.cc
@@ -0,0 +1,58 @@
+#include "sieve.hh"
+#include <cmath>
+#include <cstring>
+
+[[nodiscard]] std::vector<int> sieve1(std::size_t size) {
+  std::vector<bool> n(size, false);
+  std::vector<int> r;
+
+  for (std::size_t i = 2; i < n.size(); ++i) {
+    if (n[i] == false) {
+      r.emplace_back(i);
+      for (std::size_t j = i + i; j < n.size(); j += i)
+        n[j] = true;
+    }
+  }
+
+  return r;
+}
+
+[[nodiscard]] std::vector<int> sieve2(std::size_t size) {
+  std::vector<bool> n(size, false);
+  std::vector<int> r{2};
+
+  for (std::size_t i = 3; i < n.size(); i += 2) {
+    if (n[i] == false) {
+      r.emplace_back(i);
+      for (std::size_t j = i + i; j < n.size(); j += i)
+        n[j] = true;
+    }
+  }
+
+  return r;
+}
+
+[[nodiscard]] std::vector<int> sieve3(std::size_t size) {
+  std::vector<bool> n(size, false);
+  std::vector<int> r{2};
+
+  std::size_t s = sqrt(n.size());
+
+  for (std::size_t i = 4; i <= s; i += 2)
+    n[i] = true;
+
+  for (std::size_t i = 3; i <= s; i += 2) {
+    if (n[i] == false) {
+      r.emplace_back(i);
+      for (std::size_t j = i * i; j < n.size(); j += i)
+        n[j] = true;
+    }
+  }
+
+  s += s % 2 ? 2 : 1;
+  for (std::size_t i = s; i < n.size(); i += 2)
+    if (n[i] == false)
+      r.emplace_back(i);
+
+  return r;
+}