Question

Consider this prime sieve in which an array of numbers of size N is created (i.e. int nums[10] = {2,3,4,5,6,7,8,9,10,11};) and initialized to contain counting numbers starting with 2. The sieve works by taking each number in the array, and “crossing out” (perhaps via a similar array of Booleans) multiples of that number. So beginning with 2, we would “cross out” 4, 6, 8, 10. Then repeat the process for 3, and so on. Numbers that are already “crossed out” need not be run through the sieve, as we can prove that all of its multiples are in fact crossed out as well. Provide a pseudocode implementation for a threaded implementation of the sieve that uses N threads, with each thread "crossing out" multiples of a given prime base k.

Answer 1

Code:

#include <iostream>
#include <thread>
#include <mutex>

using namespace std;

mutex m;

void cross(int* num,bool* bCrosed,int& number, size_t& numberIndex, const int size)
{
   //Locking for each thread
   m.lock();
   for (size_t i = numberIndex; i < size; i++)
   {
       if (bCrosed[i] && num[i] % number == 0)
       {
           bCrosed[i] = false;
       }
   }
   //Unlocking the Critical section
   m.unlock();
}

int main()
{
   const int size = 10;

   int nums[size] = { 2,3,4,5,6,7,8,9,10,11 };
   bool bCrossed[size] = { true,true,true,true,true,true,true,true,true,true };
   thread t[size];

   for (size_t i = 0; i < 10; i++)
   {
       t[i] = thread(cross, nums,bCrossed,std::ref(nums[i]),std::ref(i),size);
   }

   for (size_t i = 0; i < 10; i++)
   {
       t[i].join();
   }

   cout << "\nCrossed Elements : ";

   for (size_t i = 0; i < 10; i++)
   {
       cout << std::boolalpha << bCrossed[i]<<" ";
   }
  
   return 0;
}

OUTPUT