#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <omp.h>

#define N 1000000  // Change this value as needed

void sieve_recursive(char* sieve, int start, int end, int sqrtN) {
    if (start > end) return;

    int middle = (start + end) / 2;

    #pragma omp task firstprivate(sieve, start, middle, sqrtN)
    sieve_recursive(sieve, start, middle, sqrtN);

    #pragma omp task firstprivate(sieve, middle + 1, end, sqrtN)
    sieve_recursive(sieve, middle + 1, end, sqrtN);

    #pragma omp taskwait

    for (int i = 2; i <= sqrtN; i++) {
        if (sieve[i]) {
            for (int j = fmax(i * i, (start + i - 1) / i * i); j <= end; j += i) {
                sieve[j] = 0;
            }
        }
    }
}

int main() {
    int sqrtN = sqrt(N);
    char* sieve = malloc(N);

    if (!sieve) {
        fprintf(stderr, "Memory allocation failed for sieve of size %d\n", N);
        return 1;
    }
    memset(sieve, 1, N);

    #pragma omp parallel
    {
        #pragma omp single nowait
        {
            sieve_recursive(sieve, 2, N - 1, sqrtN);
        }
    }

    // Print prime numbers
    for (int i = 2; i < N; i++) {
        if (sieve[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");

    free(sieve);
    return 0;
}