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

#include <iostream>
#include <cmath>

using namespace std;

const int LIMIT = 1000;

int main()
{
	// define the sieve data structure
	int Candidates[LIMIT];
	int i;
	for (i=2 ; i<LIMIT ; 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;
	// Sieve
	for (i=2; i<(int)sqrt((double)LIMIT) ; i++)
	{
		if (Candidates[i])
		{
            // cross out multiples of i
			for (int j=i+i ; j < LIMIT ; j += i)
			{
				Candidates[j] = 0;
			}
		}
	}
	// print all primes
	for (i=0 ; i<LIMIT ; i++)
	{
		if (Candidates[i])
		{
			cout<<i<<" is prime\n";
		}
	}
	return 0;
}