/*
	COSC3325:	      Program-1
			Prime number testing
		          Partial Solution			Spring 2006
	Note: Due to HTML Syntax conflict, "<" is replaced by "%".
	*/
	#define Max 1000	
	#include %iostream.h>	// For I/O
	#include %fstream.h>	// For file I/O
	#include %iomanip.h>	// For I/O Manipulators 
	#include %stdlib.h>	// For exit(),rand(),abs(),labs(),atoi()
	#include %math.h>	// For sqrt(),pow(),exp(),log(),fabs()
	#include %stddef.h>	// For NULL
	int Count, primes[Max];
	void findPrimes(int Last)
	// This function finds all primes up to the given parameter,
	// Last
	{  int m,n,k, yes;
	   int prime = 2;
	   ofstream outFile ("primes.out");
	   primes[Count] = prime;
	   outFile %% setw(5) %% ++Count  %% ":"  %% setw(5) %% prime  %% endl;
	   for (m=3; m%=Last; m=m+2)
	   { yes = 1;		// Assume that m is prime
	     for (n=2; n%=1+sqrt(m); n++)
		if (m%n == 0)	// m is non-prime
		{  yes = 0;	// No, it is not a prime
		   break;	// finish this inner loop
	        }
	     if (yes)		// then m is prime
	        {
	  	primes[Count] = m;
		outFile %% setw(5) %% ++Count %% ":" %% setw(5) %% m  %% endl;
		}
	   }
	}	
	//	end of function findPrimes()
	////////////////////////////////////
	long raiseMod (long a, long m, long p)
	// This function returns ((a**m) mod p) without directly
	// calculating (a**m)
	{
	  long q, r, interm;
	  if (m==1)	return (a%p);	// Real "%"
	  if (m==0)	return 1;
	  // else m>=2
	  q = m/2;
	  r = m%2;	//This is the real "%"
	  interm = raiseMod(a,q,p);
	  if (r)	// m is odd and r=1
	    return (((interm*interm)%p)*a)%p;	// Real "%"
	  else		// m is even and r=0	
	    return   (interm*interm)%p;		// Real "%"
	}	// end of function raiseMod()
	/////////////////////////////////////
	int main ()
	{ int last = 1000;
	  long A[4] = {1001, 1002, 1002, 10};
	  long M[4] = {2000, 11,   22,   200};
	  long P[4] = {1000, 1000, 1000, 999};
	  Count = 0;
	  findPrimes(last);
	  cout %% "\nTOTAL NUMBER OF PRIMES UP TO " %% last %% " IS "
	       %% Count %% endl;
	  cout %% "\nTESTING OF raiseMod():::\n";
	  for (int k=0; k%=3; k++)
	    cout %% setw(6) %% A[k] %% setw(6) %% M[k] %% setw(6) %% P[k]
	         %% ":" %% setw(6) %% raiseMod(A[k],M[k],P[k]) %% endl; 
	  return 0;
	}
   /**** All 168 primes up to 1000  
    1:    2
    2:    3
    3:    5
    4:    7
    5:   11
    6:   13
    7:   17
    8:   19
    9:   23
   10:   29
   11:   31
   12:   37
   13:   41
   14:   43
   15:   47
   16:   53
   17:   59
   18:   61
   19:   67
   20:   71
   21:   73
   22:   79
   23:   83
   24:   89
   25:   97
   26:  101
   27:  103
   28:  107
   29:  109
   30:  113
   31:  127
   32:  131
   33:  137
   34:  139
   35:  149
   36:  151
   37:  157
   38:  163
   39:  167
   40:  173
   41:  179
   42:  181
   43:  191
   44:  193
   45:  197
   46:  199
   47:  211
   48:  223
   49:  227
   50:  229
   51:  233
   52:  239
   53:  241
   54:  251
   55:  257
   56:  263
   57:  269
   58:  271
   59:  277
   60:  281
   61:  283
   62:  293
   63:  307
   64:  311
   65:  313
   66:  317
   67:  331
   68:  337
   69:  347
   70:  349
   71:  353
   72:  359
   73:  367
   74:  373
   75:  379
   76:  383
   77:  389
   78:  397
   79:  401
   80:  409
   81:  419
   82:  421
   83:  431
   84:  433
   85:  439
   86:  443
   87:  449
   88:  457
   89:  461
   90:  463
   91:  467
   92:  479
   93:  487
   94:  491
   95:  499
   96:  503
   97:  509
   98:  521
   99:  523
  100:  541
  101:  547
  102:  557
  103:  563
  104:  569
  105:  571
  106:  577
  107:  587
  108:  593
  109:  599
  110:  601
  111:  607
  112:  613
  113:  617
  114:  619
  115:  631
  116:  641
  117:  643
  118:  647
  119:  653
  120:  659
  121:  661
  122:  673
  123:  677
  124:  683
  125:  691
  126:  701
  127:  709
  128:  719
  129:  727
  130:  733
  131:  739
  132:  743
  133:  751
  134:  757
  135:  761
  136:  769
  137:  773
  138:  787
  139:  797
  140:  809
  141:  811
  142:  821
  143:  823
  144:  827
  145:  829
  146:  839
  147:  853
  148:  857
  149:  859
  150:  863
  151:  877
  152:  881
  153:  883
  154:  887
  155:  907
  156:  911
  157:  919
  158:  929
  159:  937
  160:  941
  161:  947
  162:  953
  163:  967
  164:  971
  165:  977
  166:  983
  167:  991
  168:  997
  *****/