Prime numbers with array and OpenMP in C #include &lt;stdio.h&gt;
#include &lt;string.h&gt;
#include &lt;math.h&gt;
#include &lt;omp.h&gt;

#define MAXN 10*1000*1000

int fillarray(unsigned maxn, int *p, int psize) {

    int i, top = 1;
    int n;
    p[0] = 3;
    printf(&quot; 2\n 3\n&quot;);

    for (n = 5;; n += 2)

        for (i = 0; n % p[i] != 0; i++)

            if (p[i] * p[i] &gt; n) {

                printf(&quot;%6d\n&quot;, n);
                p[top] = n;

                if (n * n &gt; maxn)
                    return top;

                if (++top == psize) {
                    printf(&quot;Array too short\n&quot;);
                    return -1;
                }

                break;
           }
}

int main() {

    unsigned n, maxn = MAXN;
    int sum;

    /* Prime Number Theorem formula (x/logx) to find approx. 
       size of array p[]. Needs some safety margin. */
    int psize =  10 + 1.2 * sqrt(maxn) / log(sqrt(maxn));
    int p[psize], *pp;

    int lastp = fillarray(maxn, p, psize);
    if (lastp &lt; 0)
        return 1;

    /* &quot;3&quot; is p[0], plus the &quot;2&quot; */
    sum = lastp + 2;

    #pragma omp parallel for private(pp) schedule(guided) reduction(+:sum)

    for (n = p[lastp] + 2; n &lt;= maxn; n += 2)

        for (pp = p; n % *pp &gt; 0; pp++)

            if (*pp * *pp &gt; n) {
                printf(&quot;%d\n&quot;, n);
                sum++;
                break;
            }


    printf(&quot;SUM %d (%.2f%%)\n&quot;, sum, (double) 100*sum / maxn) ;
    double lnx = maxn / log(maxn);
    printf(&quot;LnX %.2f (%f)\n&quot;,  lnx, sum / lnx);
    printf(&quot;psize %d\n&quot;, psize);
    printf(&quot;p[0] p[1]...p[%d] %d %d...%d\n&quot;, lastp, p[0], p[1], p[lastp]);

    return 0;
}

Compile with -fopenmp. And -lm for clang. But it works also without openmp.
Output:
# time ./a.out |tail
9999971
9999901
9999931
9999973
9999991
9999937
SUM 664579 (6.65%)
LnX 620420.69 (1.071175)
psize 480
p[0] p[1]...p[445] 3 5...3163

real    0m0.274s
user    0m1.497s
sys     0m0.402s

It takes 445 primes to reach 3163, whose square is &gt; 10 million. The array size is 480. The output is not sorted, the threads print them directly.
The first (single-threaded) phase i.e. fillarray() takes no time compared to second, multi-threaded phase.
In main() the prime test is inlined, and written with pointers.
A couple of minor things.
For int psize, consider using size_t.
log(sqrt(maxn)) should simply be log(maxn)/2, which is equivalent.