#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <pthread.h>

#define THREAD_NUM 3
#define DATA_NUM 100

typedef struct _thread_arg {
    int id;
    bool *primes;
} thread_arg_t;

void *
thread_func(void *arg)
{
    thread_arg_t *targ = (thread_arg_t *)arg;

    int range = (DATA_NUM - 2) / THREAD_NUM + 1;
    int c_start = 2 + targ->id * range;
    int c_end = 2 + (targ->id + 1) * range;
    if (c_end > DATA_NUM) c_end = DATA_NUM;

    for (int i = c_start; i < c_end; i++) {
        int limit = (int)sqrt((double) i);
        for (int j = 2; j <= limit; j++) {
            if (targ->primes[j] && i % j == 0){
                targ->primes[i] = false;
                break;
            }
        }
    }
    return 0;
}

int
main()
{
    pthread_t handle[THREAD_NUM];
    thread_arg_t targ[THREAD_NUM];
    bool primes[DATA_NUM];

    /* initialize */
    for (int i = 0; i < DATA_NUM; i++) primes[i] = true;

    for (int i = 0; i < THREAD_NUM; i++) {
        targ[i].id = i;
        targ[i].primes = primes;
        pthread_create(&handle[i], NULL,&thread_func, (void*)&targ[i]);
    }

    /* wait for running all thread */
    for (int i = 0; i < THREAD_NUM; i++) pthread_join(handle[i], NULL);

    for (int i = 2; i < DATA_NUM; i++)
        if (primes[i]) printf("%d ", i);
    printf("\n");

    return 0;
}