#include <iostream>
#include <bitset>


using namespace::std;

int main()
{

	const int maxprime = 10000;


	bitset < maxprime + 1 > primes;



	cout << "Using a total of " << sizeof(primes) << "bytes for the array\n\n";

	primes.set();
	//Set all bits to 1 (prime)
	primes.reset(0);
	//Set bits 0 and 1 to 0 (non prime)
	primes.reset(1);

	for (int i = 2; i * i <= maxprime; i++) {	//Only check to the square root of Maxprime

		if (!primes[i]) {	//If a number is composite, all of it's multiples are already set as composite
			continue;
		}

		for (int j = 2 * i; j <= maxprime; j += i) {
			//Go from the first multiple of i all the way to maxprime
			primes[j] = 0;
		}

	}



	for (int i = 0; i <= maxprime; i++) {

		if (primes[i]) {
			cout << i << "\n";
		}


	}

	return 0;
}