/// GH Working the sieve of eratosthenes


/*
 * C++ Program to implement Sieve of Eratosthenes
 */

#include <iostream>
#include <vector>

using namespace std;

unsigned sqroot(unsigned );

const unsigned len = sqroot(UINT_MAX);

void printPrimes(vector<unsigned> );

bool is_theorem_true(vector<unsigned> );

int main()
{
    vector<bool> primesErat(len,true);
    // Use Sieve of Eratosthenes to get primes
    for (unsigned i = 2; i < sqroot(len); )
    {
        for (unsigned j = i * i; j < len; j+=i)
            primesErat[j] = false;
        while(!primesErat[++i]);  ///skip on to next prime
    }
    //Build vector of primes, primeList[0] = 2
    //primeList[13] = 43;
    vector<unsigned> primeList;
    for(unsigned i = 2; i < primesErat.size(); ++i)
        if(primesErat[i]==true) primeList.push_back(i);
    cout << "\nprimeList[13] = " << primeList[13];
    //printPrimes(primeList);
    cout << "\nThe theorem is " << is_theorem_true(primeList);
}

void printPrimes(vector<unsigned> v) {
    for (unsigned i = 2; i < v.size(); i++)
        //if (v[i] == true)
        cout << v[i] << "\t";
}

unsigned sqroot(unsigned n) {
    double toler = 1.e-12*n;
    double temp{n/2};
    double next{(temp+n/temp)/2.};
    while(temp-next>toler || next-temp>toler) {
        temp = next;
        next = (temp+n/temp)/2.;
    }
    return unsigned(next);
}


bool is_theorem_true(vector<unsigned> prime) {
    unsigned leastOf6{286};//, prime43orMore;
    bool still_true = true;
    int cntr{0};
    while(leastOf6 < len-7) { //while within 6
        cntr = 0;
        still_true = false;
        while(cntr<6 && !still_true) {
            for(int i = 13; prime[i] <= (leastOf6+cntr)/2+1 && !still_true; ++i) {
                //cout << "\nChecking if " << leastOf6+cntr << " % " << prime[i] << " = 0" << (leastOf6+cntr)%prime[i] ;
                if((leastOf6+cntr)%prime[i]==0) {
                    cout << endl << leastOf6+cntr << "%" << prime[i] << " = 0";
                    leastOf6 += cntr+1;
                    //cntr = 0;
                    cin.get();
                    cout << "\ngap = " << cntr;
                    still_true = true;
                }
            }
            ++cntr;
            //if(cntr==6) return false;
            //cin.get();
        }

    }
}