1

私は持っている：

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);
     }
4

2 に答える 2

4

あなたが望むものは些細なことではありません。しかし、ここでは 2 つのスレッドについて考え、調査し、テストするためのアイデアを示します。

これを行うには、2 つのスレッド間でジョブを「分割」する必要があります。たとえば、最初のスレッドで の間[ 2, k ]の素数を検索し、2 番目のスレッドで の間の素数を検索するようにします[ k+1, x ]。

これは些細な部分でした。ここで問題が発生します - どうやって見つけるのxですか？（kかんたん～x / 2）。

たとえば、特定の間隔で素数の数を見つける方法などを調査する必要があります。これは役に立つかもしれません：それはあなたが使用できると言います：

N ~~ x / ln(x)

ここNで、 は x より小さい素数の数です。

ええと、私は数学者ではないので、今すぐ解決策を提供することはできませんが、Nを見つけなければならない方法があるはずxです。

これは多数の場合にうまく機能することに注意してください。

したがって、これを使用すると、x が見つかったら、2 つのスレッド間でジョブを分割できます。

xご覧のとおり、これは本当に些細なことではなく、 ( )を見つけるための正確な (正確な) メソッドはありませんN。

もちろん、もう 1 つの些細な方法 (そしてはるかに簡単ですが、それほど良い方法ではありません) は、 の範囲を知り、Nそれを 2 つの間隔に分割することです。または、最初の、たとえば 100 個の素数を見つけることは大したことではありません。しかし、最初の 1000 を見つけることは別のことです。この場合、たとえば、+500 個の素数ごとに追加のスレッドを開始することができます。

N別のアイデアは、 - 番目の素数の近似値を見つけるための調査を行うことです。それが役立つかもしれません: n 番目の素数のおおよその値を見つける方法はありますか?

于 2013-04-01T07:37:48.273 に答える