//Generates Prime using Seive of Eratosthenes Idea

#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::cin;

//Helper
typedef unsigned int uInt; 
typedef std::vector<bool> boolVec;

//Generates Prime using Seive of Eratosthenes Idea
void SeivePrime(const uInt MAX)
{
	if(MAX < 1 || MAX > INT_MAX){
		throw std::invalid_argument("Number not within range[2,INT_MAX] to call SeivePrime(const unsigned int)\n\n");
	}

	boolVec Prime(MAX + 1, true);
	//0,1 is not a Prime
	Prime[0] = Prime[1] = false;
	
	uInt nextPrime = 2;	
	bool deleteComplete = false;

	//Heart of the code
	//Helps generate prime numbers
	while(nextPrime <= MAX)
	{
		//delete all multiple of nextPrime		
		for(uInt i = 2; !deleteComplete; i++)	{			
			if( nextPrime * i > MAX  )
				deleteComplete = true;
			else Prime[nextPrime * i] = false;
		}

		//reset for next use
		deleteComplete = false;

		//Find next prime
		++nextPrime;
		while(nextPrime <= MAX && !Prime[nextPrime]) { 			
			++nextPrime;
			continue;
		}		
	
	}

	//Display Prime
	uInt i = 0;
	while(i <= MAX)	
	{		
	   if(Prime[i])
	     cout<< i <<" is a Prime\n";						
	   ++i;
	}

}
int main()
{ 

	try	{		
		SeivePrime(1438);
	}
	catch(std::exception& e){
		cout << e.what() <<endl;
	}
	
	return 0;

}