//////////////////////////////////////////////////////////
// Name: Peter M. Maurer
// Program: Sieve of Eratosthenes
// Due: Never
// Language: C++
//////////////////////////////////////////////////////////

#include <iostream>

using namespace std;

int main()
{
	// define the sieve data structure
	int Candidates[1000];
	int i;
	for (i=0 ; i<1000 ; i++)
	{
		// everything is potentially prime until proven otherwise
		Candidates[i] = 1;
	}
	// Neither 1 nor 0 is prime, so flag them off
	Candidates[0] = 0;
	Candidates[1] = 0;
	// start the sieve with the integer 0
	i = 0;
	while (i<1000)
	{
		// advance to the next un-crossed out number.
		// this number must be a prime
		while (i<1000 && Candidates[i] == 0)
		{
			i++;
		}
		// insure against running off the end of the data structure
		if (i<1000)
		{
			// cross out all multiples of the prime, starting with 2*p.
			int j;
			for (j=2 ; j*i < 1000 ; j++)
			{
				Candidates[j*i] = 0;
			}
			// advance to the next candidate
			i++;
		}
	}
	// all uncrossed-out numbers are prime (and only those numbers)
	// print all primes
	for (i=0 ; i<1000 ; i++)
	{
		if (Candidates[i] != 0)
		{
			cout<<i<<" is prime\n";
		}
	}
	return 0;
}