Prime numbers with array and OpenMP in C

Question

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

#define MAXN 10*1000*1000

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

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

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

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

            if (p[i] * p[i] > n) {

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

                if (n * n > maxn)
                    return top;

                if (++top == psize) {
                    printf("Array too short\n");
                    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 < 0)
        return 1;

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

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

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

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

            if (*pp * *pp > n) {
                printf("%d\n", n);
                sum++;
                break;
            }


    printf("SUM %d (%.2f%%)\n", sum, (double) 100*sum / maxn) ;
    double lnx = maxn / log(maxn);
    printf("LnX %.2f (%f)\n",  lnx, sum / lnx);
    printf("psize %d\n", psize);
    printf("p[0] p[1]...p[%d] %d %d...%d\n", 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 > 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.

Answer 1

A couple of minor things.

For int psize, consider using size_t.

log(sqrt(maxn)) should simply be log(maxn)/2, which is equivalent.