/* Linda (POSYBL) 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

*/

int N, /* check primes from 2 to N */
    Chunk, /* how many numbers to check at one time */
    NNodes, /* number of nodes in computation*/
    Me;  /* id of this node*/

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

{  int J,CJ;

   for (J = 2; J*J <= K; J++)  {
      /* if J is known to be composite, don't bother dividing by it */
      rd(lstring("composite"),lint(J),qlint(&CJ));
      if (!CJ)  if (K % J == 0) return 1;
   }
   return 0;
}

Worker()

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

   Block = NNodes * Chunk;

   First = 1 + Me * Chunk;
   Last = First + Chunk - 1;
   NIters = N / Block;
   for (Iter = 0; Iter < NIters; Iter++)  {
      for (I = First; I <= Last; I++)  
         if (IsComposite(I))  {
            /* need to REMOVE I-th composite tuple, update it and
	       put it back; note that it won't be available to
	       other workers during the update */
            in(lstring("composite"),lint(I),qlint(&CI));
            CI = 1;
            out(lstring("composite"),lint(I),lint(CI));
	    MyComposites++;
	 }
      First += Block;  Last += Block;
   }

   /* need atomic access to Composite[0], but this is easy
      with Linda, without locks, because we temporarily remove
      the tuple from the tuple space, so no one else can access
      it */
   in(lstring("composite"),lint(0),qlint(&C0));
   C0 += MyComposites;
   out(lstring("composite"),lint(0),lint(C0));

   /* set up indirect barrier */
   out(lstring("done"));
}

main()

{  int NArgs,I,C0,Node,Debug;

   /* get info from front end */
   /* find AND REMOVE a tuple matching "whoami" in the first component,
      and decode the second component into the integer Me */
   in(lstring("whoami"),qlint(&Me));
   /* find BUT DO NOT REMOVE a tuple matching "number of workers"
      in the first component, and decode the second component into
      the integer NNodes */
   rd(lstring("number of workers"),qlint(&NNodes));
   /* find BUT DO NOT REMOVE a tuple matching "argument" in the 
      first component and 0 in the second component, and decode the 
      third component into the integer N */
   rd(lstring("argument"),lint(0),qlint(&N));
   /* similarly for Chunk and Debug */
   rd(lstring("argument"),lint(1),qlint(&Chunk));
   rd(lstring("argument"),lint(2),qlint(&Debug));

   while(Debug) ;
  
   /* set up the composite `array' (a bunch of tuples), with
      `Composite[I]' = 0; but make sure to do it only once,
      not at every node */
   if (Me == 0)
      for (I = 0; I <= N; I++) out(lstring("composite"),lint(I),lint(0));

   Worker();

   /* node 0 will print the results, but need to make sure everyone 
      is done first (indirect barrier) */
   if (Me == 0)  {
      for (Node = 0; Node < NNodes; Node++)
         in(lstring("done"));
      in(lstring("composite"),lint(0),qlint(&C0));
      printf("number of primes = %d\n",N-C0-1);
   }

   /* to avoid system hanging */
   out(lstring("front end may exit"));

}