"The Genuine Sieve of Eratosthenes" in C++14
At least to me, this seems a little like another instance of the same basic problem pointed out in linked paper: although there are a few parts that I guess are sort of neat, overall it strikes me as a huge amount of code to solve a trivial problem, and (at least based on the numbers you're posting) apparently runs really slowly.

It doesn't attempt to make much in the way of style points, but lets consider sort of a reference implementation--roughly the simplest thing that works to some degree:

#include &lt;vector&gt;
#include &lt;iostream&gt;
#include &lt;locale&gt;

unsigned long primes = 0;

int main() {
    int number = 20'000'000;
    std::vector&lt;bool&gt; sieve(number,false);
    sieve[0] = sieve[1] = true;

    for(int i = 2; i&lt;number; i++) {
        if(!sieve[i]) {
            ++primes;
            for (int temp = 2*i; temp&lt;number; temp += i)
                sieve[temp] = true;
        }
    }
    std::cout.imbue(std::locale(""));
    std::cout &lt;&lt; "found: " &lt;&lt; primes &lt;&lt; " Primes\n";
    return 0;
}


On my notebook (4 or 5 years old, and wasn't tremendously fast when it was new) this finds 1,270,607 primes in 147 milliseconds (so in round numbers, it's running something like 75 or 80 times as fast as the code in the question). Even compared to @Toby's optimized version, it's still something like 20 times faster.

Don't get me wrong: I'm all for using nice algorithms and making code generic where it's reasonable--and I'm pretty sure there are ways to do that in this case without paying much of a penalty. But, at least to me, it seems to me as if the code you presented is paying a pretty high penalty--and given its much greater length and overall complexity, I'm not convinced we're getting any real improvement in return for that speed penalty either.

I'd re-emphasize that this is not really optimized code, or anything like that either--we can do quite a bit better by taking the square root into account, using a segmented sieve, and switching to something like a sieve of Atkins, and using a more specialized bit vector instead of std::vector&lt;bool&gt;. If we did those, we could probably expect to improve speed by around another order of magnitude (and depending on the number of primes we decided to find, maybe even more than that).