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
---
 sieve.cc | 58 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 58 insertions(+)
 create mode 100644 sieve.cc

(limited to 'sieve.cc')

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