/*
 *
 * 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();
}