#include <stdio.h>
#include <omp.h>
#include <stdbool.h>
#include <math.h>

void sieveOfEratosthenes(int n) {
    bool prime[n+1];
    #pragma omp parallel for
    for (int i = 0; i <= n; i++) {
        prime[i] = true;
    }

    int sqrt_n = (int)sqrt(n);
    #pragma omp parallel for
    for (int p = 2; p <= sqrt_n; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= n; i += p) {
                prime[i] = false;
            }
        }
    }

    #pragma omp parallel for
    for (int p = 2; p <= n; p++) {
        if (prime[p]) {
            #pragma omp critical
            printf("%d ", p);
        }
    }
}

int main() {
    int n = 10000;
    printf("Prime numbers up to %d are: ", n);
    sieveOfEratosthenes(n);
    printf("\n");

    return 0;
}