// ENGR 131 - Monday 3:30 Recitation (Amanda Rohn)
// Assignment #6 - Sieve of Eratosthenes
// 
// Finds all primes between 1 and 999
//
// Solution

#include <iostream>

using std::cout;

int main()
{
	// declare constant for number of values in the array
	// this is good programming practice because it makes it much easier
	// to later change my program and make it find primes in a different range -
	// I don't need to go in and change the other values that depend on n

	const int n = 1000;

	// array of boolean values will tell whether that number has been crossed out (true)
	// or is still a possible prime (false)

	bool crossed[n] = {false};	

	// In this for-loop, i refers to the current prime, and
	// j*i is (clearly) a multiple of i.

	// If j is a multiple of i, it can't be prime, so we "cross it out" (set crossed[j*i] to true)

	for(int i = 2; i < n/2; i++)
	{
		if(!crossed[i])
		{
			for(int j = 2; j*i <= n; j++)
			{
				crossed[j*i] = true;
			}
		}
	}

	// print the primes

	for(int k = 1; k < n; k++)
	{
		if(!crossed[k])
		{
			cout << k << '\n';
		}
	}

	return 0;
}