// http://stackoverflow.com/questions/231381/
// is-this-prime-generator-inefficient-c/235517#235517
// by ephemient, answered Oct 24 '08 at 22:45
// + my edits, 2012-05-16 (1. odds; 2. stages) -- WillNess
#include <iostream>
#include <map>
using namespace std;
template<typename T = int, typename M = map<T, T> >
class odd_prime_iterator {
public:
odd_prime_iterator() : current(1), skips() { operator++(); }
T operator*() { return current; }
odd_prime_iterator &operator++() {
typename M::iterator i;
while ((i = skips.find( (current+=2) )) != skips.end()) {
T skip = i->second, next = current + skip;
skips.erase(i);
for (typename M::iterator j = skips.find(next);
j != skips.end(); j = skips.find(next += skip)) {}
skips[next] = skip;
}
skips[current * current] = 2 * current;
return *this;
}
private:
T current;
M skips;
};
template<typename T = int, typename M = map<T, T> >
class staged_prime_iterator {
public:
staged_prime_iterator() : current(1), skips(), base() // base starts from 3
{ q = *base * *base; operator++(); }
T operator*() { return current; }
staged_prime_iterator &operator++() {
while ( 1 )
{
current += 2;
if( current == q )
{
add_a_skip( current + 2 * *base, 2 * *base);
++base;
q = *base * *base;
continue;
}
typename M::iterator i = skips.find( current );
if( i == skips.end() ) // not found among the multiples - current is prime
break;
T skip = i->second, next = current + skip;
skips.erase(i);
add_a_skip( next, skip);
}
return *this;
}
T show_base(){ return *base; }
private:
T current, q;
M skips;
odd_prime_iterator<T> base;
void add_a_skip( T next, T skip ) {
for (typename M::iterator j = skips.find(next);
j != skips.end(); j = skips.find(next += skip)) {}
skips[next] = skip;
}
};
int main() {
staged_prime_iterator<int> primes;
// cout << 2 << " ";
int i = 1;
for (int k=1; *primes < 10000000-100; ++primes, ++i) ;
for (int k=1; *primes < 10000000; ++primes, ++i)
{
if( k++ == 20 ) { cout << endl; k = 1; }
cout << *primes << " ";
}
cout << endl << *primes
<< " {{ " << i << " primes, base = " << primes.show_base() << " }}";
return 0;
}