# Prime numbers with array and OpenMP in C

#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)

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.

• "The first (single-threaded) phase i.e. fillarray() takes no time compared to second, multi-threaded phase." So your question is to have an explanation why? Or do you ask for generally potential improvements of your code? Oct 27, 2020 at 10:33
• Indeed, what is the question? You show some code; very good. It can be compiled; even better. But you haven't asked us anything... Oct 28, 2020 at 9:27

For int psize, consider using size_t.
log(sqrt(maxn)) should simply be log(maxn)/2, which is equivalent.
• Thanks, both makes sense. I was not aware of the equivalence. Don't even know if it should be, but yes, it really could be log(maxn)/2. I would add a third comment line - for unmathematical people like myself!