// JUMP/JIAJIA example program:  find number of primes between 2 and N;
// uses the Sieve of Eratosthenes, deleting all multiples of 2, all
// multiples  of 3, all multiples of 5, etc.  

// disclaimer:  not claimed to be efficient; at the very least, the NI
// operation should be in chunks

#include <stdio.h>
#include <math.h>
#include <jia.h>
 
// pointers to shared variables
int *Prime;  // Prime[I] = 1 if I prime, else 0
int *NextI;  // pointer to next I to be checked
int *NDone;  // pointer to number of nodes done with the job
// lock indices for the shared variables
#define NEXTI_LOCK 0
#define NDONE_LOCK 1 

int N,  // range to check for primeness
    Debug;  // 1 for debugging, 0 else

CrossOut(int K)

{  int I;

   for (I = 2; I*K <= N; I++)  {
      Prime[I*K] = 0;
   }
}

DoWork()

{  int Lim,NI,IAmDone=0;

   // no need to check divisors bigger than sqrt(N)
   Lim = sqrt(N);

   do  {
      // get next divisor, avoiding duplication
      jia_lock(NEXTI_LOCK);
      NI = (*NextI)++;
      jia_unlock(NEXTI_LOCK);
      if (!IAmDone)  { 
         if (NI <=  Lim)  {
            // don't bother with the crossouts if NI is known to be
            // composite; note that it's not a problem if Prime[NI] is not
            // fully up to date
            if (Prime[NI])  
               CrossOut(NI);
         }
         else  {
            IAmDone = 1; 
            jia_lock(NDONE_LOCK);
            (*NDone)++;
            jia_unlock(NDONE_LOCK);
         }
      }
      // force an update
      jia_barrier();
   } while (*NDone < jiahosts);
}

main(int ArgC, char **ArgV)

{  int NPrimes,  // number of primes found 
       MyWait = 0,  // kind of a debugger "barrier"
       I;

   jia_init(ArgC,ArgV);  // this must be called first

   // jiapid is the JIAJIA ID number for this node; note that
   // command-line arguments are shifted for nodes other than 0 
   if (jiapid == 0)  {
      N = atoi(ArgV[1]);
      Debug = atoi(ArgV[2]);   
   }
   else  { 
      N = atoi(ArgV[2]);
      Debug = atoi(ArgV[3]);   
   }

   // set up shared variables
   jia_barrier();
   Prime = (int *) jia_alloc(N*sizeof(int));
   NextI = (int *) jia_alloc(sizeof(int));
   NDone = (int *) jia_alloc(sizeof(int));
   if (Prime == 0 || NextI == 0)  {
      printf("jia_alloc() failure\n");
      exit(1);
   }
   jia_barrier();

   if (jiapid == 0)  {
      // make them all prime until shown otherwise
      for (I = 2; I <= N; I++) 
         Prime[I] = 1;
      *NextI = 2;
      *NDone = 0;
   }
   // everyone else wait for node 0 to finish init
   jia_barrier();

   // if debugging, have everyone wait here and then set MyWait to 1 by
   // hand 
   if (Debug)
      while (MyWait == 0)  { ; }
   
   DoWork();

   // don't need a barrier here, due to the one in DoWork() 
   if (jiapid == 0)  {
      NPrimes = 0;
      for (I = 2; I <= N; I++)
         if (Prime[I]) NPrimes++;
      printf("the number of primes found was %d\n",NPrimes);
   }

   jia_exit();
}