#include <iostream>
#include <cmath>
#include <vector>  // much better than bitset: see Tw7DO
 
using namespace std;   // by stackoverflow.com/users/849891/will-ness
 
int main()  // sieve of Eratosthenes, upto a value,              **** OLD TIMINGS ****
{           // on one contiguous array, as vector<bool>, 
            //                                for ODDS ONLY
  const size_t topval = // 541;    // C++        //  haskell:
     //  primes upto N in value    vector<bool>  roll/gaps/Wh   ARR/Odds  STUArray/Odds
     //                            FaPOB (this)     Ojq01        RzqLP        KwZNc
     //      7919;  //   1,000:                                 
     //   1000003;  //  78,499:                                 0.04  4.8
     //   1299709;  // 100,000:                                 
     //   2750159;  // 200,000:                                 0.09  4.8
     //   5800079;  // 400,000:                                 0.21  5.8
     //  15485863;  // 1 mln:       0.06s-2.7MB   1.38s 4.7MB   0.67  7.8   0.43  4.8
     //  32452843;  // 2 mln:       0.16s-2.7MB   3.25s 4.7MB   2.16 11.9   0.98  5.8
     //  49979687;  // 3 mln:       0.29s-2.7MB   5.40s 4.7MB   
     //  67867967;  // 4 mln:       0.47s-2.7MB   7.68s 4.7MB   5.63 24.2   2.31  8.9 
     //  86028121;  // 5 mln:       0.63s-2.7MB  10.08s 4.7MB               3.04  9.9 
     // 104395301;  // 6 mln:       0.79s-2.7MB  12.66s 4.7MB   9.84 39.6   3.79 10.9
     // 113648393;  // 6.5 mln:     0.86s-2.7MB                             4.14 10.9
     // 122949823;  // 7 mln:                                  12.20 36.5
     // 133000999;  // 7538613:     1.04s-2.7MB                             4.95 11.9
     // 141650939;  // 8 mln:       1.11s-2.7MB                14.61 40.6   5.32 13.0
     // 334214459;  // 18 mln:      2.89s-2.7MB                            13.65 24.2
     // 1000000007; // 50,847,535:  9.45s-2.7MB
     // 1500000101; // 74,726,535: 14.55s-2.7MB
     // 1505800000; // 75,001,089: 14.74s-2.7MB 
     // 1505776939; // 75 mln      14.61s-2,7MB
     //     3  -  6  -  18  -  50  -  74    million primes:  
     // ~ n^ 1.45   1.18   1.14   1.12    empirical orders of growth
     //   20000000; // 1,270,607 primes: 0.09s-3.3M (new ideone engine, 2014-01-04)
     
                      // 75 mln    primes: 5.67s             **** 2018-02-25 TIMINGS ****
     //  2050000000;  // 100556393 primes: 7.96s  ~n^1.16 
         1000000000;   //                              ~N^1.10

  size_t n   = topval/2 + 1;           // NATS: (topval+1)
  size_t m   = 250;                    // print out primes in top 500 of range
  size_t cnt = n;                      // count the primes
 
  vector<bool> s;   // <char> 2x slower, same memory reported for 100M test run
  s.resize(n, true);                   // all potential primes are ON
  
  size_t itop = ceil( (sqrt(2*n+1)-1)/2 ); // mark off multiples of first primes upto sqrt
  
  for( size_t i=1; i <= itop; ++i )    // I=3,5.. , I=2i+1, i=1,2..
  {
    if( s[i] )                         // I*I -1 /2 = 4i^2+4i+1 -1 /2 = 2i(i+1)
      for( size_t j=2*i*(i+1); j<n; j += i+i+1 )   // I*I, +2I, +4I, ...
        if( s[j] )                     
        {                              
          s[j] = false;                // mark the composites OFF
          --cnt;
        }
  }
 
  if( 2 <= topval && n <= m )          // 2 is a first prime 
      cout << 2;
  
  for( size_t k=(n>m?n-m:1), c=0;      // print out some last primes 
        k < n; ++k ) 
    if( s[k] )                   
    {
      cout << " " << 2*k + 1;
      if( (++c % 8) == 0) 
        cout << endl;
    }
  
  cout << endl  
       << cnt  << " primes found." << endl;

  return 0;
}