Code

#include <iostream>
#include <time.h>
#include <pthread.h>

using namespace std;

int n,k;
bool isPrime[1000010];

//Method to generate primes
//The implementation could've been done more efficiently but it was implemented this way
//so that the execution time difference gets amplified further so the distinction is clear.
void *genPrimes(void *arg){
    long rem=(long)arg;
    for(int i=rem;i<n;i+=k)
        if(i>1){
            int factorCnt=0;
            for(int j=1;j<=i;++j)
                if(!(i%j))
                    ++factorCnt;
            if(factorCnt==2)
                isPrime[i]=true;
        }
    pthread_exit(NULL);
}

//Driver method
int main(){
    //Required variables
    clock_t start,end;
    time_t t;
    srand((unsigned)time(&t));
    float execTime=0;

    //Taking input
    cout<<"Enter the number N : ";
    cin>>n;

    cout<<"Enter the number of threads : ";
    cin>>k;

    //Thread array
    pthread_t threads[k];

    //creating threads and assigning them work
    start=clock();
    for(int i=0;i<k;++i)
        pthread_create(&threads[i], NULL, genPrimes, (void *)i);

    for(int i=0;i<k;++i)
        pthread_join(threads[i],NULL);
    end=clock();

    execTime=((double)(end-start)/CLOCKS_PER_SEC);

    cout<<endl<<"The primes are : "<<endl;
    for(int i=0;i<=n;++i)
        if(isPrime[i])
            cout<<i<<" ";
    cout<<endl;
    cout<<endl<<"Execution time is : "<<execTime<<endl;
    return 0;
}