calculate how many number of prime number under n.

calPrime.hpp

#ifndef cal_prime_hpp
#define cal_prime_hpp
extern int cal_prime_number_under_n(int);
#endif

main.cpp

#include <iostream>
#include <vector>
#include "calPrime.hpp"
using namespace std;

int main() {

#if defined(v1) || defined(v2) || defined(v3)
    int N = 100000; // # of prime num under 100k is 9592
#elif defined(sieve_v1) || defined(sieve_v2) || defined(sieve_v3)
    // int N = 10000000; // # of prime num under 10M is 664579
    int N = 100000000; // # of prime num under 100M is 5761455
#else
    int N = 1000000; // # of prime num under 1M is 78498
#endif
    cout<< "# of prime number under " << N << " : " << cal_prime_number_under_n(N) <<endl;

    return 0;
}

Makefile

cxx_source = main.cpp prime.cpp sieve.cpp

all: prog prog_task prog_task_pthread \
	 prog_sieve prog_sieve_task prog_sieve_task_thread

prog: $(cxx_source)
	g++ -Dv1 $^ -o $@
	time ./$@

prog_task: $(cxx_source)
	g++ -Dv2 $^ -o $@
	time ./$@

prog_task_pthread: $(cxx_source)
	g++ -Dv3 $^ -lpthread -o $@
	time ./$@

prog_sieve: $(cxx_source)
	g++ -Dsieve_v1 $^ -o $@
	time ./$@

prog_sieve_task: $(cxx_source)
	g++ -Dsieve_v2 $^ -o $@
	time ./$@

prog_sieve_task_thread: $(cxx_source)
	g++ -std=c++11 -Dsieve_v3 $^ -o $@
	time ./$@

clean:
	rm prog*

prime.cpp

#include "calPrime.hpp"
#include <vector>
using namespace std;

#if defined(v1)
int cal_prime_number_under_n(int n) {
    vector<int> prime_vec;
    for(int i=2; i<=n ;i++) {
        int j;
        for(j=0; j<prime_vec.size(); j++) {
            if( i%prime_vec[j]==0) {
                break;
            }
        }
        if(j==prime_vec.size()) {
            prime_vec.push_back(i);
        }
    }
    return prime_vec.size();
}
#elif defined(v2)
static bool is_prime(int t) {
    for(int i=2; i<=t/2; i++) {
        if(t%i==0) return false;
    }
    return true;
}

int cal_prime_number_under_n(int n) {
    int num = 0;
    for(int i=2; i<=n ;i++) {
        if(is_prime(i)) {
            num++;
        }
    }
    return num;
}
#elif defined(v3)
#include <pthread.h>
#define NUM_THREADS 4

typedef struct thread_param
{
    int seed;
    int terminate_number;
    int result;
} tparam_t;

static bool is_prime(int t) {
    for(int i=2; i<=t/2; i++) {
        if(t%i==0) return false;
    }
    return true;
}

void *threadFunc(void *pArg) {
    int seed = ((tparam_t *)pArg)->seed;
    int term = ((tparam_t *)pArg)->terminate_number;
    int num = 0;
    for(int i = seed; i<=term ;i+=NUM_THREADS) {
        if(is_prime(i)) {
            num++;
        }
    }
    ((tparam_t *)pArg)->result = num;
    return NULL;
}

int cal_prime_number_under_n(int n) {
    pthread_t tHandles[NUM_THREADS];
    tparam_t tParam[NUM_THREADS];

    for(int i=0; i<NUM_THREADS; i++) {
        tParam[i].seed = 2+i;
        tParam[i].terminate_number = n;
        pthread_create(&tHandles[i], NULL, threadFunc, (void*) &tParam[i]);
    }

    int num = 0;
    for(int j=0; j<NUM_THREADS; j++) {
        pthread_join(tHandles[j], NULL);
        num+=tParam[j].result;
    }
    return num;
}
#endif

sieve.cpp

#include "calPrime.hpp"
#include <vector>
using namespace std;

#if defined(sieve_v1)
int cal_prime_number_under_n(int n) {
    vector<bool> prime_vec(n+1, true);
    prime_vec[0] = false;
    prime_vec[1] = false;
    for(int i=2; i<=n ;i++) {
        if(prime_vec[i]) {
            for(int j=2*i; j<prime_vec.size(); j+=i) {
                prime_vec[j] = false;
            }
        }
    }
    int num = 0;
    for(int i=0; i<prime_vec.size(); i++) {
        if(prime_vec[i]) num++;
    }
    return num;
}
#elif defined(sieve_v2)
vector<bool> prime_vec;

void filterout_composite_number(int base) {
    for(int j=2*base; j<prime_vec.size(); j+=base) {
        prime_vec[j] = false;
    }
}

int cal_prime_number_under_n(int n) {
    prime_vec.resize(n+1, true);
    prime_vec[0] = false;
    prime_vec[1] = false;
    for(int i=2; i<=n ;i++) {
        if(prime_vec[i]) {
            filterout_composite_number(i);
        }
    }
    int num = 0;
    for(int i=0; i<prime_vec.size(); i++) {
        if(prime_vec[i]) num++;
    }
    return num;
}
#elif defined(sieve_v3)
#include <thread>
#define NUM_THREADS 4

typedef struct thread_param {
    vector<bool> prime_vec;
    int base;
} tparam_t;

void filterout_composite_number(tparam_t *pArgs) {
    vector<bool> &prime_vec = pArgs->prime_vec;
    int base = pArgs->base;
    for(; base<prime_vec.size(); base+=NUM_THREADS) {
        if(!prime_vec[base]) continue;
        for(int j=2*base; j<prime_vec.size(); j+=base) {
            prime_vec[j] = false;
        }
    }
}

int cal_prime_number_under_n(int n) {

    vector<thread> tHandles(NUM_THREADS);
    vector<tparam_t> tParams(NUM_THREADS);

    for(int i=0; i<NUM_THREADS; i++) {
        // thread parameter initialization
        // Be aware that data complexity is O(n) for each thread.
        tParams[i].prime_vec.resize(n+1, true);
        tParams[i].prime_vec[0] = false;
        tParams[i].prime_vec[1] = false;
        tParams[i].base = i;
        tHandles[i] = thread(filterout_composite_number, &tParams[i]);
    }

    for(int j=0; j<NUM_THREADS; j++) {
        tHandles[j].join();
    }

    // reduce: combine the thread data
    vector<bool> prime_vec;
    prime_vec.resize(n+1, true);
    for(int i=0; i<prime_vec.size(); i++) {
        for(int j=0; j<NUM_THREADS; j++) {
            if(!tParams[j].prime_vec[i]) {
                prime_vec[i] = false;
                break;
            }
        }
    }

    int num = 0;
    for(int i=0; i<prime_vec.size(); i++) {
        if(prime_vec[i]) num++;
    }
    return num;
}
#endif