// 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) -- WillNess
#include <iostream>
#include <map>
using namespace std;
/* odds
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 prime_iterator {
public:
prime_iterator() : current(2), skips() { skips[4] = 2; } // original code
T operator*() { return current; }
prime_iterator &operator++() {
typename M::iterator i;
while ((i = skips.find(++current)) != 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] = current;
return *this;
}
private:
T current;
M skips;
};
int main() {
/*odd_*/prime_iterator<int> primes;
// cout << 2 << " ";
int i=0;
for (int k=1; *primes < 10000000-100; ++primes, ++i) ;
for (int k=1; *primes < 10000000; ++primes, ++i)
{
cout << *primes << " ";
if( ++k == 20 ) { cout << endl; k = 0; }
}
cout << endl << *primes << " n=" << i;
return 0;
}