2
\$\begingroup\$
#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.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ "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? \$\endgroup\$ Oct 27, 2020 at 10:33
  • 1
    \$\begingroup\$ Indeed, what is the question? You show some code; very good. It can be compiled; even better. But you haven't asked us anything... \$\endgroup\$
    – Jim Cownie
    Oct 28, 2020 at 9:27

1 Answer 1

1
\$\begingroup\$

A couple of minor things.

For int psize, consider using size_t.

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

\$\endgroup\$
4
  • 1
    \$\begingroup\$ @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++. \$\endgroup\$
    – Reinderien
    Oct 27, 2020 at 16:41
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – pacmaninbw
    Oct 27, 2020 at 16:44
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Reinderien
    Oct 27, 2020 at 17:18
  • \$\begingroup\$ 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! \$\endgroup\$
    – user232411
    Oct 28, 2020 at 15:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.