fork download
copy 
  1. // http://stackoverflow.com/questions/231381/
  2. //    is-this-prime-generator-inefficient-c/235517#235517
  3.  
  4. // by ephemient, answered Oct 24 '08 at 22:45  
  5. // + my edits, 2012-05-16 (1. odds) -- WillNess
  6.  
  7. #include <iostream>
  8. #include <map>
  9.  
  10. using namespace std;
  11.  
  12. /* odds
  13.  
  14. template<typename T = int, typename M = map<T, T> >
  15. class odd_prime_iterator {
  16.         public:
  17.             odd_prime_iterator() : current(1), skips() { operator++(); }
  18.             T operator*() { return current; }
  19.             odd_prime_iterator &operator++() {
  20.                 typename M::iterator i;
  21.                 while ((i = skips.find( (current+=2) )) != skips.end()) {
  22.                     T skip = i->second, next = current + skip;
  23.                     skips.erase(i);
  24.                     for (typename M::iterator j = skips.find(next);
  25.                             j != skips.end(); j = skips.find(next += skip)) {}
  26.                     skips[next] = skip;
  27.                 }
  28.                 skips[current * current] = 2 * current;
  29.                 return *this;
  30.             }
  31.         private:
  32.             T current;
  33.             M skips;
  34.     };
  35. */
  36.  
  37. template<typename T = int, typename M = map<T, T> >
  38. class prime_iterator {
  39.         public:
  40.             prime_iterator() : current(2), skips() { skips[4] = 2; }   // original code
  41.             T operator*() { return current; }
  42.             prime_iterator &operator++() {
  43.                 typename M::iterator i;
  44.                 while ((i = skips.find(++current)) != skips.end()) {
  45.                     T skip = i->second, next = current + skip;
  46.                     skips.erase(i);
  47.                     for (typename M::iterator j = skips.find(next);
  48.                             j != skips.end(); j = skips.find(next += skip)) {}
  49.                     skips[next] = skip;
  50.                 }
  51.                 skips[current * current] = current;
  52.                 return *this;
  53.             }
  54.         private:
  55.             T current;
  56.             M skips;
  57. };
  58.  
  59.  
  60. int main() {
  61.         /*odd_*/prime_iterator<int> primes;
  62.         // cout << 2 << " ";
  63.         int i=0;
  64.         for (int k=1; *primes < 10000000-100; ++primes, ++i) ;
  65.         for (int k=1; *primes < 10000000; ++primes, ++i)
  66.         {
  67.             cout << *primes << " ";
  68.             if( ++k == 20 ) { cout << endl; k = 0; }
  69.         }
  70.         cout << endl << *primes << " n=" << i;
  71.         return 0;
  72. }
Success #stdin #stdout 7.3s 23584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9999901 9999907 9999929 9999931 9999937 9999943 9999971 9999973 9999991 
10000019 n=664246
https://ideone.com/0fgMu
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!