// Assignment: sieve.cpp
// Purpose: To write the most efficient program
// that outputs prime numbers.

#include<iostream.h>
#include<iomanip.h>
#include<math.h>
// declare constant MAX_NUMBER to be the # of arrays.
const MAX_NUMBER = 1000;


// declare array primes.
bool primes[MAX_NUMBER];
// function prototypes
void initializeArray();
void findMultiples();
void printSubscripts();

int main()
{
// call to functions
initializeArray();
findMultiples();
printSubscripts();
return 0;
}

//*****************************************************
// function initializeArray
//
// Purpose: to initialize the Aray
//
// Input: none
// Output: none
void initializeArray()
{
// start from index 2, ignoring 1 and 0
for(int index = 0; index < MAX_NUMBER; index++)
primes[index] = true;
primes[0] = false;
primes[1] = false;
}

//*****************************************************
// function findMultiples
//
// Purpose: assign false to multiples of prime numbers
//
// Input: none
// Output: none
void findMultiples()
{
int steps = 0;
// for loop, starting the primes at 2, incrementing every loop
for(int index = 2; index < sqrt(MAX_NUMBER); index++)
// if true, then continue
if(primes[index] == true)
// all multiples of primes are assigned false
for(int multiplier = 2; multiplier * index < MAX_NUMBER; multiplier++)
{


primes[multiplier * index] = false;
steps++;
}
cout << "Number of steps are : " << steps << endl;
}



//*****************************************************
// function printSubscripts
//
// Purpose: print prime numbers to console
//
// Input: none
// Output: prime numbers
void printSubscripts()
{
cout << "The prime numbers from 1 to " << MAX_NUMBER-1 << " are:\n" << endl;
// output primes starting from primes[2]
for(int index = 0; index < MAX_NUMBER; index++)
{
if(primes[index])
// a "tab" between every prime number.
cout << index << "\t";
}
cout << endl;
}

typedef unsigned int UINT4;

void GetRandomA(UINT4 *a, UINT4 n)
{
*a = rand() % (n - 2) + 1;
}

/* Rabin/Miller test to test a prime number.
Taken from Larry Frieson's Password Manager.
n - 1 = 2km for some k > 0 and odd integer m.
a = 1 < a < n - 1
We say that n passes the Rabin-Miller test for the base a if
either the first term in this sequence is 1, or 1 occurs later
in this sequence and is immediately preceded by -1. If the test
fails, we know that n is composite, and describe the base a as
a witness to the compositeness of n. The crucial extra information
we can derive is that if (odd) n is composite, then at least 3/4
of the numbers a with 1 < a < n - 1 are witness to this fact.
First calculate m, in C++ we do this by simply shifting the bits
right k times, until m is odd and less than n.
Next, we calculate a, such that a is less than n - 1, and a > 1.
Then, we calculate a ^ m mod n. If this result is 1, then
we need to generate a new a and try again. After iIterations, we
can say that n is prime with 1/1024 margin of error.

Two function prototype follow, one for 32 bit integers, one for
multi-precision integers.
*/

int RabinMiller(UINT4 n, int iIterations)
{
srand(100);
int isprime = 0;
UINT4 m = n - 1;
UINT4 k = 0;
UINT4 a = 0;
if((n & 1) == 0) {
return 0;
}
if(m > 0) {
while((m & 1) == 0)
{
k++;
m = (m >> 1);
}
}
GetRandomA(&a, n);
UINT4 r;
do
{
r = 1;
for (int i = 0; i < m; i++)
{
r = (r * a) % n;
}
if(r == 1 || r == (n - 1)) {
GetRandomA(&a, n);
isprime = 1;
continue;
}
for(UINT4 x = 0;x < k + 1;x++)
{
r = (r*r) % n;
if(r == (n - 1)) {
isprime = 1;
break;
}
}
if(isprime == 0) {
break;
}
GetRandomA(&a, n);
}
while(iIterations--);
return isprime;
}

for(int x = 0;x < 9999;x++)
{
int isPrime = RabinMiller(x, 5);
}