add Sieve algo for finding prime numbersHEADmaster

1 files changed, 130 insertions, 0 deletions

diff --git a/PrimeCPP.cpp b/PrimeCPP.cpp
new file mode 100644
index 0000000..7f9bd71
--- /dev/null
+++ b/PrimeCPP.cpp
@@ -0,0 +1,130 @@
+/*
+ *
+ * compile:  clang++ -march=native -mtune=native -Ofast -std=c++17 PrimeCPP.cpp -o Primes_clang++.exe
+ *
+ */
+
+
+#include <chrono>
+#include <ctime>
+#include <iostream>
+#include <fstream>
+#include <bitset>
+#include <map>
+#include <cstring>
+#include <cmath>
+
+using namespace std;
+using namespace std::chrono;
+
+// array of bits initially set all to 1's and then selectively set to false as each composite (non prime number) gets market
+class BitArray {
+    uint32_t *array;
+    size_t arrSize;
+
+    inline static size_t arraySize(size_t size) {
+        return (size >> 5) + ((size & 31) > 0);
+    }
+
+    inline static size_t index(size_t n) {
+        return (n >> 5);
+    }
+
+    inline static uint32_t getSubindex(size_t n, uint32_t d) {
+        return d & uint32_t(uint32_t(0x01) << (n % 32));
+    }
+
+    inline void setFalseSubindex(size_t n, uint32_t &d) {
+        d &= ~uint32_t(uint32_t(0x01) << (n % (8*sizeof(uint32_t))));
+    }
+public:
+    explicit BitArray(size_t size) : arrSize(size) {
+        array = new uint32_t[arraySize(size)];
+        std::memset(array, 0xFF, (size >> 3) + ((size & 7) > 0));
+    }
+
+    ~BitArray() {delete [] array;}
+
+    bool get(size_t n) const {
+        return getSubindex(n, array[index(n)]);
+    }
+
+    void set(size_t n) {
+        setFalseSubindex(n, array[index(n)]);
+    }
+};
+
+class prime_sieve
+{
+  private:
+
+      long sieveSize = 0;
+      long primeCount = 0;
+      BitArray Bits;
+
+   public:
+
+      prime_sieve(long long n) 
+        : Bits(n), sieveSize(n)
+      {
+      }
+
+      ~prime_sieve()
+      {
+      }
+
+      void runSieve(std::chrono::time_point<std::chrono::steady_clock> tStart)
+      {
+          int prime = 2;
+          int q = (int) sqrt(sieveSize);
+
+          while (prime <= q)
+          {
+            for (int num = prime; num < sieveSize; num++)
+            {
+              if (Bits.get(num))
+              {
+                prime = num;
+                this->primeCount++;
+
+                // mark all composites
+                for (int comp = prime * 2; comp < sieveSize; comp += prime)
+                  Bits.set(comp);
+              }
+            }
+          }
+
+          auto duration = duration_cast<microseconds>(steady_clock::now() - tStart).count() / 1000000.0;
+
+          printf("Time: %lf, Limit: %ld, Primes Found: %ld\n", duration, this->sieveSize, this->primeCount);
+      }
+
+      void writeResults(void)
+      {
+          std::ofstream outfile("primes.txt", std::ios::out);
+          if (outfile.is_open())
+          {
+            outfile << "2, ";
+            int count = (sieveSize >= 2);  // Starting count (2 is prime)
+            for (int num = 3; num <= sieveSize; num+=2)
+            {
+              if (Bits.get(num))
+                outfile << num << ", ";
+            }
+
+            outfile << std::endl;
+            outfile.close();
+          }
+          else
+            std::cout << "Unable to open a file for writing" << std::endl;
+      }
+};
+
+int main()
+{
+    auto tStart = steady_clock::now();
+
+    prime_sieve sieve(1000000000LL);
+    sieve.runSieve(tStart);
+    sieve.writeResults();
+}