/* TupleDSM sample program; NOT INTENDED TO BE EFFICIENT as a prime
   finder, either in algorithm or implementation 

   finds and reports the number of primes less than or equal to N

   each node works on a range of Chunk numbers at a time, testing
   them for primeness by straight division; if a potential divisor
   has already been found to be composite (i.e. nonprime), then we
   skip it

*/

#include <DSMInclude.h>

#define MAX_N 1000

int N, /* check primes from 2 to N */
    Chunk, /* how many numbers to check at one time */
    Composite[MAX_N], /* array of composites found so far, code 1 for 
                         composite, 0 otherwise */
    Debug;

int IsComposite(K)  /* returns 1 if K is found to be composite */
   int K;

{  int J;

   for (J = 2; J*J <= K; J++)  {
      /* if J is known to be composite, don't bother dividing by it */
      DSMSharedReadRequest("Composite",Composite,J);
      DSMSharedReadRelease("Composite",Composite,J);
      if (!Composite[J])  
         if (K % J == 0) return 1;
   }
   return 0;
}

Worker()

{  int First,Last,Iter,NIters,I,Node,Block,MyComposites = 0;

   Block = DSMTotNodes * Chunk;

   First = 1 + DSMNodeNum * Chunk;
   Last = First + Chunk - 1;
   NIters = N / Block;
   for (Iter = 0; Iter < NIters; Iter++)  {
      for (I = First; I <= Last; I++)  
         if (IsComposite(I))  {
            DSMNonExclWriteRequest("Composite",Composite,I);
	    Composite[I] = 1;
            DSMNonExclWriteRelease("Composite",Composite,I);
	    MyComposites++;
	 }
      First += Block;  Last += Block;
   }

   /* Composite[0] will store the total number of composites */
   DSMExclWriteRequest("Composite",Composite,0); 
   Composite[0] += MyComposites;
   DSMExclWriteRelease("Composite",Composite,0); 
}

main(int argc,char **argv)

{  DSMEnvInit();
   if (DSMNodeNum == 0)  {
      DSMVarInit("Composite",MAX_N);
      DSMBarrierCreate("join barrier");
   }
   N = atoi(DSMArgv[1]);
   Chunk = atoi(DSMArgv[2]);
   Debug = atoi(DSMArgv[3]);

   while (Debug) ;

   Worker();

   /* need to make sure everyone is done before printing 
      out the results */
   DSMBarrier("join barrier"); 
   if (DSMNodeNum == 0)  {
      DSMredReadRequest("Composite",Composite,0);
      printf("number of primes = %d\n",N-Composite[0]-1);
   }
   DSMExit();
}