#include <iostream>
#include <thread>
#include <vector>
#include <math.h>
#include <memory>
#include <chrono>

using namespace std;
using namespace std::chrono;
typedef high_resolution_clock::time_point TimePoint;

void PerformSieve(bool* sieve, int start, int inc, int max)
{
   for (int i = start; i <= (int)sqrt(max); i+=inc)
   {
      if (sieve[i])
      {
         for (int j = i * i; j <= max; j += i)
         {
            sieve[j] = false;
         }
      }
   }
}

// Use the Sieve of Eratosthenes to find all primes up to a certain integer.
// This algorithm is implemented sequentially.
bool* FindPrimeSieveSequential(int n)
{
   bool* sieve = (bool*)calloc(n, sizeof(bool));
   std::fill_n(sieve, n, true);

   PerformSieve(sieve, 3, 2, n);

   // At this point, the indices of all false values in the sieve array
   // represent composite numbers.
   // The values in all even indices should be ignored; all evens are composite.
   // All remaining indices with true values are prime.
   return sieve;
}

// Use the Sieve of Eratosthenes to find all primes up to a certain integer.
// This algorithm is implemented using parallelism.
bool* FindPrimeSieveInParallel(int n, int numThreads)
{
   bool* sieve = (bool*)calloc(n, sizeof(bool));
   std::fill_n(sieve, n, true);

   // Declare array of threads and run sieve on them.
   thread threads[numThreads];
   for (int i = 0; i < numThreads; i++)
   {
      threads[i] = thread(PerformSieve, sieve, 3 + i, numThreads, n);
   }

   // Join the threads with the main thread.
   for (int i = 0; i < numThreads; i++)
   {
      threads[i].join();
   }

   // At this point, the indices of all false values in the sieve array
   // represent composite numbers.
   // The values in all even indices should be ignored; all evens are composite.
   // All remaining indices with true values are prime.
   return sieve;
}

int main(int argc, char *argv[])
{
//   unique_ptr<Counter> counter = make
   int n = 100000000;

   TimePoint t1 = high_resolution_clock::now();
//   FindPrimeSieveSequential(n);
   FindPrimeSieveInParallel(n, 8);
   TimePoint t2 = high_resolution_clock::now();

   auto duration = duration_cast<milliseconds>(t2 - t1).count();
   cout << duration << endl;

   return 0;
}