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.

• πάντα ῥεῖ: "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?
• Jim Cownie: Indeed, what is the question? You show some code; very good. It can be compiled; even better. But you haven't asked us anything...

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.

• Reinderien: @AryanParekh I'm not really sure what you're asking, but 1. I learned both C and C++, the latter first; and 2. much (but not all) of the C language and its best practices can be understood "automatically" by someone who is already familiar with C++.
• pacmaninbw: @AryanParekh C++ is backwards compatible with C for a reason, C++ originally started out as C with classes. Another thing you need to keep in mind when programming in C is not to use C++ keywords so that the program can be ported to C++ at a later time.
• Reinderien: @AryanParekh Let's move this discussion to chat.stackexchange.com/rooms/115582/re-c-c-compatibility - it's not particularly on-topic for the current answer.
• user232411: 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!