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


struct Parameters {
    int left; // left end of the segment
    int right; // right end of the segment
    int size; // sqrt(n)
    int *max_printed_number; // the biggest right end of printed segment
    int *amount_of_working_threads; // amount of working threads
    bool *first_numbers; // prime-not prime boolean array on first sqrt(n) numbers
};


const int max_memory_size = 100000; // maximal memory for all threads
const int limit = INT_MAX; // maximal number we are working with
const int retries = 1; // amount of testing retrying for time counting
pthread_attr_t attr;


int min(int a, int b) {
    if (a < b) {
        return a;
    }
    return b;
}


int max(int a, int b) {
    if (a > b) {
        return a;
    }
    return b;
}


int integer_sqrt(int n) {
    return (int)ceil(sqrt(n));
}


int myCeil(int numerator, int denominator) {
    return (numerator - 1) / denominator + 1;
}


void * eratosphen_initialisation(bool* first_sqrt_numbers, int size) {
    for (int i = 0; i <= size; ++i) {
        first_sqrt_numbers[i] = true;
    }
    for (int i = 2; i <= size; ++i) {
        if (first_sqrt_numbers[i]) {
            for (int j = 2 * i; j <= size; j += i) {
                first_sqrt_numbers[j] = false;
            }
        }
    }
    for (int i = 2; i <= size; ++i) {
        if (first_sqrt_numbers[i]) {
            printf("%d\n", i);
        }
    }
    return NULL;
}



void * eratosphen_iteration(void* vp) {
    printf("I entered the function\n");
    struct Parameters* p = (struct Parameters*)vp;
    int segment_size = p->right - p->left + 1;
    bool* new_segment = (bool*) malloc(sizeof(bool) * segment_size);
    // за число k отвечает индекс k - p->left;
    for (int i = 0; i < segment_size; ++i) {
        new_segment[i] = true;
    }
    int j = 0;
    printf("I'm in function\n");
    for (int i = 2; i <= p->size; ++i) {
        if (p->first_numbers[i]) {
            printf("%d is prime\n", i);
            j = myCeil(p->left, i) * i - p->left;
            for (; j < segment_size; j += i) {
                printf("%d is not prime\n", j);
                new_segment[j] = false;
            }
        }
    }
    while ((*(p->max_printed_number)) + 1 != p->left) {
        //wait
    }
    for (int i = 0; i < segment_size; ++i) {
        if (new_segment[i]) {
            printf("%d\n", i + p->left);
        }
    }
    free(new_segment);
    *(p->max_printed_number) = p->right;
    (*(p->amount_of_working_threads))--;
    return NULL;
}

void eratosphenus(int threads_num, int n) {
    int max_printed_number = 0;
    int max_given_number = 0;
    int first_elements_amount = integer_sqrt(n);
    bool* first_numbers = (bool*) malloc(sizeof(bool) * (first_elements_amount + 1));
    printf("First elements amount -- %d\n", first_elements_amount);
    //sqrt(INT_MAX) = 2**16 = 65536 - is not really big, so I didn't parallelize this
    eratosphen_initialisation(first_numbers, first_elements_amount);
    max_given_number = first_elements_amount;
    max_printed_number = max_given_number;
    // Here our first sqrt(n) elements are ready

    int max_thread_memory = myCeil(min(max_memory_size, n), threads_num);
    pthread_t *threads = (pthread_t *) malloc(sizeof(pthread_t) * threads_num);
    struct Parameters* parameters = (struct Parameters*) malloc(sizeof(struct Parameters)
                                                                * threads_num);
    int amount_of_working_threads = 0;
    int next_max_given_number = 0;
    int next_free_thread = 0;
    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
    printf("max_given_number -- %d; max_printed_number -- %d\n", max_given_number, max_printed_number);
    printf("I am here\n");
    while (max_given_number < n) {
        if (amount_of_working_threads < threads_num) {
            next_max_given_number = min(max_given_number, n - max_thread_memory) + max_thread_memory;
            struct Parameters new_parameter = {max_given_number + 1, next_max_given_number, n,
                                               &max_printed_number, &amount_of_working_threads};
            parameters[next_free_thread % threads_num] = new_parameter;
            pthread_create(threads + (next_free_thread  % threads_num), &attr,
                           eratosphen_iteration, &parameters[next_free_thread  % threads_num]);
            printf("Created from %d to %d\n", max_given_number + 1, next_max_given_number);
            amount_of_working_threads++;
            next_free_thread++;
            max_given_number = next_max_given_number;
        }
    }
    printf("I finished\n");
    free(first_numbers);
    free(parameters);
    free(threads);
}


int main(int argc, char** argv) {
    int n = 0;
    if (argc == 2) {
        n = limit;
    }
    else {
        n = atol(argv[2]);
    }
    int threads_num = atol(argv[1]);
    threads_num = min(threads_num, n); // No reason to have threads more than numbers
    //clock_t start, end;
    //start = clock();
    for (int i = 0; i < retries; ++i) {
        eratosphenus(threads_num, n);
    }
    //end = clock();
    //printf("%f seconds", (float)(end- start)/retries/CLOCKS_PER_SEC);
    return 0;
}