Multithreaded prime number generator

Question

I have:

input1: n to generate primes up to
input2: no of threads to generate primes

I implemented this and it works, but the problem is, that each thread generates its own list of primes [2, n].

But I want both threads to work on the same task of generating prime numbers, switching with each other, not independently. How to divide n into number of threads?

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void *BusyWork(void *threadid)
{
long tid;
tid = (long)threadid;
printf("Hello World! It's me, thread # %ld\n", tid);

double s,d;
int n,i,c,k,p,cs,nsqrt;     
printf( "Input an integer n > 1 to generate primes upto this n:   " ); // prompt 
scanf("%d",&n); 
printf( "Entered integer: %d\n",n);
int array[n];
for(i=0;i<n;i++)
    array[i]=0;
s=sqrt(n);
d=floor(s);
nsqrt = (int) d;

for ( c= 2; c <= nsqrt; c++ )// note here < is not working <= is working here.
    {
        if(array[c]==0)
            {
                cs = c*c;
                k=0;
                for(p=cs; p<n; p=(cs+k*c))
                    {
                        k++;
                        array[p] = 1;
                }//for
            }//if
    }//for

    for ( i = 2; i < n; i++ )
    { 
        if (array[i]==0)
        {
            printf("%5d",i);
        }//if
    }// for
    printf("\n");


    printf("Above prime numbers are generated from me i.e. thread # %ld GOOD BYE!!! \n ", tid);


    pthread_exit((void*) threadid);
    }

  int main (int argc, char *argv[])
  {

   //////// time cal ///////////////////

     struct timespec start, finish;
     double elapsed;

      clock_gettime(CLOCK_MONOTONIC, &start);
     /////////////////////////////////////

    int NUM_THREADS;
     printf("Please Input Total Number of Threads you want to make:-  ");
     scanf("%d",&NUM_THREADS);


     pthread_t thread[NUM_THREADS];
     pthread_attr_t attr;
       int rc;
     long t;
     void *status;

       /* Initialize and set thread detached attribute */
     pthread_attr_init(&attr);
       pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);

      for(t=0; t<NUM_THREADS; t++) {
        printf("Main: creating thread %ld\n", t);
        rc = pthread_create(&thread[t], &attr, BusyWork, (void *)t); 
        if (rc) {
           printf("ERROR; return code from pthread_create() is %d\n", rc);
           exit(-1);
          }
        }

      /* Free attribute and wait for the other threads */
       pthread_attr_destroy(&attr);
      for(t=0; t<NUM_THREADS; t++) {
       rc = pthread_join(thread[t], &status);
      if (rc) {
       printf("ERROR; return code from pthread_join() is %d\n", rc);
       exit(-1);
       }
       printf("Main: completed join with thread %ld having a status of %ld\n",t,  (long)status);
      }

  printf("Main: program completed. Exiting.\n");
   ////////////// time end ////////////////////////
    clock_gettime(CLOCK_MONOTONIC, &finish);

   elapsed = (finish.tv_sec - start.tv_sec);
      elapsed += (finish.tv_nsec - start.tv_nsec) / 1000000000.0;
   printf("Total time spent by the main:  %e \n", elapsed);
    //////////////////////////////////////////////////////////
   pthread_exit(NULL);
     }

Answer 1

What you want is far from trivial. But here's an idea for thinking, research and testing for two threads.

To do this, you need to "split" the job between the two threads. For example, make the first thread to look for prime numbers between [ 2, k ] and make the second thread to look for primes between [ k+1, x ].

This was the trivial part. Here comes the problem - how to find x? (k is easy - x / 2).

You should research for - how to find number of prime numbers in a given interval, for example. This could be useful: it says, that you may use:

N ~~ x / ln(x)

where N is the number of primes, less than x.

Well, I'm not a mathematician and I can't give you right now the solution, but there should be a way, having N to find x.

Note, that this works fine for large numbers.

So, having this, once you find x, you will be able to split the job between the two threads.

As you see, this is really far from trivial and there's no exact (precise) method for finding x (N).

---

Of course, the other trivial way (and a lot easier but not that good) is to know the range of N and just split it into two intervals. Or, finding the first, say, 100 primes is not a big deal. But finding the first 1000 is something else. In this case, you may just start additional threads for each +500 prime numbers, for example.

---

Another idea is to do a research for finding approximation of the N-th prime number. That may help: Is there a way to find the approximate value of the nth prime?

Answer 2

Apologies if I have misinterpreted your post, but I suspect that you have misunderstood what multi threading is about. Your code and last question suggests that you think that starting multiple identical threads means that they somehow automatically divide the task up between themselves. This is fundamentally not correct. We all wish that it was, but it isn't.

There are several approaches. There is the 'manual' approach where you exploit opportunities for parallelism in your problem and write a thread for each bit (or start the same thread several times with different parameters. Either way the threads+data are not identical). You can then run those threads in parallel. In essence this is the approach that Kirol Kirov suggested.

An alternative that can work quite well for mathematical problems with long loops is to use a compiler that can automatically decompose the loop into separate threads at runtime. This means you write ordinary single threaded code and tell the compiler to generate threads wherever it can determine that it is safe to do so. Saves you a lot of work and in the right circumstances produces effective results. The Sun C compiler can do this on Solaris and the Intel one can do it too (maybe only on Windows). Some research into the latest and greatest maybe worthwhile. However, this won't teach you anything about multi threaded programming.

Another approach is to use something like openMPI which (I think) allows you to put #pragma statements in before for loops to say that you'd like tile loop executed in parallel. Kinda like the manual version of what the Intel and Sun compilers can do.