c - 多线程质数生成器

Question

我有:

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

我实现了这个并且它有效，但是问题是，每个线程生成它自己的素数列表[2, n]。

但我希望两个线程都处理生成质数的相同任务，相互切换，而不是独立运行。如何将n分成线程数？

#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

您想要的远非微不足道。但这里有一个针对两个线程进行思考、研究和测试的想法。

为此，您需要在两个线程之间“拆分”作业。例如，让第一个线程在 [ 2, k ] 之间寻找素数，让第二个线程在 [ k+1, x ] 之间寻找素数。

这是微不足道的部分。问题来了——如何找到x？ (k 很简单 - x/2)。

您应该研究 - 例如，如何找到给定区间内素数的数量。 This可能有用:它说，你可以使用:

N ~~ x / ln(x)

其中 N 是小于 x 的素数个数。

好吧，我不是数学家，我现在不能给你解决方案，但应该有办法，让 N 找到 x。

请注意，这适用于大量数据。

因此，有了这个，一旦找到 x，您就可以在两个线程之间拆分作业。

如您所见，这真的很重要，并且没有找到 x (N) 的确切(精确)方法。

---

当然，另一种简单的方法(更简单但不是那么好)是知道 N 的范围并将其分成两个区间。或者，找到第一个，比方说，100 个质数并不是什么大问题。但是找到前 1000 个是另一回事。例如，在这种情况下，您可以为每个 +500 个质数启动额外的线程。

---

另一个想法是进行一项研究，以找到第 N 个素数的近似值。这可能有帮助:Is there a way to find the approximate value of the nth prime?