/// GH working PPP4 exercise 13
/**********
13. Create a program to find all the prime numbers between 1 and 100.
There is a classic method for doing this, called the “Sieve of Eratosthenes.”
If you don’t know that method, get on the web and look it up.
Write your program using this method.
***************/

#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;

int Max = 10000;

void showPrimes(vector<bool>&);

int main() {
    vector<bool> primes(Max,1);
    primes[0] = 0;
    primes[1] = 0;
    for(int i = 2;i<sqrt(Max);) {
        for(int j = i;j<=Max/i;++j) {
            primes[j*i]=0;
            ///cout << "\nprimes[" << j*i << "]=" << primes[i*j];
        }
        while(!primes[++i]); ///keep incrementing i until we get to the next prime
    }
    showPrimes(primes);

}

void showPrimes(vector<bool>& p) {
    for(int i = 0; i < p.size(); ++i)
        if(p[i]==1)
            cout << i << " ";
}