/* Program that uses the Sieve Method of Eratosthenes to find
 * all prime numbers in a given range.  
 * Uses the standard C++ bitset class template.
 *
 * Input:  A positive integer n
 * Output: Primes in the range 2 through n
 *********************************************************/

#include <iostream>
#include <cassert>
#include <bitset>
using namespace std;

int main()
{
  const int MAX_PRIME = 20;  // limit on size of n

  int n;
  cout << "This program finds primes in the range 2 - n."
          "\nEnter positive integer n <= " << MAX_PRIME << ": ";
  cin >> n;
  assert(n > 0 && n <= MAX_PRIME);
  
  // Construct bitset sieve of size MAX_PRIME + 1 containing all ones.
  // For convenience, we are not using positions 0 and 1 of sieve so
  // the bit i represents positive integer i.

  bitset<MAX_PRIME + 1> sieve;
  sieve.set();

  // Apply the Sieve Method
  int prime = 2;         // the next prime in sieve
  while (prime * prime <= n)
  { 
    // cross out multiples of prime from sieve
    for (int mult = 2*prime; mult <= n; mult += prime)
      sieve.reset(mult);

    // find next uncrossed number in sieve
    do
      prime++;
    while (!sieve.test(prime));
  }

  // Display the list of primes.
  cout << "\nPrimes in the range 2 through " << n << ":\n";
  for (int i = 2; i <= n; i++)
    if (sieve.test(i))
      cout << i << "  ";  
  cout << sieve << endl;
  for (int i = 2; i <= n; i++)
    if (sieve.test(i))
      cout << i << "  ";

  cout << sieve.to_string() << endl;
}