#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;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDx2ZWN0b3I+ICAvLyBtdWNoIGJldHRlciB0aGFuIGJpdHNldDogc2VlIFR3N0RPCiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsgICAvLyBieSBzdGFja292ZXJmbG93LmNvbS91c2Vycy84NDk4OTEvd2lsbC1uZXNzCiAKaW50IG1haW4oKSAgLy8gc2lldmUgb2YgRXJhdG9zdGhlbmVzLCB1cHRvIGEgdmFsdWUsICAgICAgICAgICAgICAqKioqIE9MRCBUSU1JTkdTICoqKioKeyAgICAgICAgICAgLy8gb24gb25lIGNvbnRpZ3VvdXMgYXJyYXksIGFzIHZlY3Rvcjxib29sPiwgCiAgICAgICAgICAgIC8vICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmb3IgT0REUyBPTkxZCiAgY29uc3Qgc2l6ZV90IHRvcHZhbCA9IC8vIDU0MTsgICAgLy8gQysrICAgICAgICAvLyAgaGFza2VsbDoKICAgICAvLyAgcHJpbWVzIHVwdG8gTiBpbiB2YWx1ZSAgICB2ZWN0b3I8Ym9vbD4gIHJvbGwvZ2Fwcy9XaCAgIEFSUi9PZGRzICBTVFVBcnJheS9PZGRzCiAgICAgLy8gICAgICAgICAgICAgICAgICAgICAgICAgICAgRmFQT0IgKHRoaXMpICAgICBPanEwMSAgICAgICAgUnpxTFAgICAgICAgIEt3Wk5jCiAgICAgLy8gICAgICA3OTE5OyAgLy8gICAxLDAwMDogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAvLyAgIDEwMDAwMDM7ICAvLyAgNzgsNDk5OiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDAuMDQgIDQuOAogICAgIC8vICAgMTI5OTcwOTsgIC8vIDEwMCwwMDA6ICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgCiAgICAgLy8gICAyNzUwMTU5OyAgLy8gMjAwLDAwMDogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAwLjA5ICA0LjgKICAgICAvLyAgIDU4MDAwNzk7ICAvLyA0MDAsMDAwOiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIDAuMjEgIDUuOAogICAgIC8vICAxNTQ4NTg2MzsgIC8vIDEgbWxuOiAgICAgICAwLjA2cy0yLjdNQiAgIDEuMzhzIDQuN01CICAgMC42NyAgNy44ICAgMC40MyAgNC44CiAgICAgLy8gIDMyNDUyODQzOyAgLy8gMiBtbG46ICAgICAgIDAuMTZzLTIuN01CICAgMy4yNXMgNC43TUIgICAyLjE2IDExLjkgICAwLjk4ICA1LjgKICAgICAvLyAgNDk5Nzk2ODc7ICAvLyAzIG1sbjogICAgICAgMC4yOXMtMi43TUIgICA1LjQwcyA0LjdNQiAgIAogICAgIC8vICA2Nzg2Nzk2NzsgIC8vIDQgbWxuOiAgICAgICAwLjQ3cy0yLjdNQiAgIDcuNjhzIDQuN01CICAgNS42MyAyNC4yICAgMi4zMSAgOC45IAogICAgIC8vICA4NjAyODEyMTsgIC8vIDUgbWxuOiAgICAgICAwLjYzcy0yLjdNQiAgMTAuMDhzIDQuN01CICAgICAgICAgICAgICAgMy4wNCAgOS45IAogICAgIC8vIDEwNDM5NTMwMTsgIC8vIDYgbWxuOiAgICAgICAwLjc5cy0yLjdNQiAgMTIuNjZzIDQuN01CICAgOS44NCAzOS42ICAgMy43OSAxMC45CiAgICAgLy8gMTEzNjQ4MzkzOyAgLy8gNi41IG1sbjogICAgIDAuODZzLTIuN01CICAgICAgICAgICAgICAgICAgICAgICAgICAgICA0LjE0IDEwLjkKICAgICAvLyAxMjI5NDk4MjM7ICAvLyA3IG1sbjogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgMTIuMjAgMzYuNQogICAgIC8vIDEzMzAwMDk5OTsgIC8vIDc1Mzg2MTM6ICAgICAxLjA0cy0yLjdNQiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgNC45NSAxMS45CiAgICAgLy8gMTQxNjUwOTM5OyAgLy8gOCBtbG46ICAgICAgIDEuMTFzLTIuN01CICAgICAgICAgICAgICAgIDE0LjYxIDQwLjYgICA1LjMyIDEzLjAKICAgICAvLyAzMzQyMTQ0NTk7ICAvLyAxOCBtbG46ICAgICAgMi44OXMtMi43TUIgICAgICAgICAgICAgICAgICAgICAgICAgICAgMTMuNjUgMjQuMgogICAgIC8vIDEwMDAwMDAwMDc7IC8vIDUwLDg0Nyw1MzU6ICA5LjQ1cy0yLjdNQgogICAgIC8vIDE1MDAwMDAxMDE7IC8vIDc0LDcyNiw1MzU6IDE0LjU1cy0yLjdNQgogICAgIC8vIDE1MDU4MDAwMDA7IC8vIDc1LDAwMSwwODk6IDE0Ljc0cy0yLjdNQiAKICAgICAvLyAxNTA1Nzc2OTM5OyAvLyA3NSBtbG4gICAgICAxNC42MXMtMiw3TUIKICAgICAvLyAgICAgMyAgLSAgNiAgLSAgMTggIC0gIDUwICAtICA3NCAgICBtaWxsaW9uIHByaW1lczogIAogICAgIC8vIH4gbl4gMS40NSAgIDEuMTggICAxLjE0ICAgMS4xMiAgICBlbXBpcmljYWwgb3JkZXJzIG9mIGdyb3d0aAogICAgIC8vICAgMjAwMDAwMDA7IC8vIDEsMjcwLDYwNyBwcmltZXM6IDAuMDlzLTMuM00gKG5ldyBpZGVvbmUgZW5naW5lLCAyMDE0LTAxLTA0KQogICAgIAogICAgICAgICAgICAgICAgICAgICAgLy8gNzUgbWxuICAgIHByaW1lczogNS42N3MgICAgICAgICAgICAgKioqKiAyMDE4LTAyLTI1IFRJTUlOR1MgKioqKgogICAgIC8vICAyMDUwMDAwMDAwOyAgLy8gMTAwNTU2MzkzIHByaW1lczogNy45NnMgIH5uXjEuMTYgCiAgICAgICAgIDEwMDAwMDAwMDA7ICAgLy8gICAgICAgICAgICAgICAgICAgICAgICAgICAgICB+Tl4xLjEwCgogIHNpemVfdCBuICAgPSB0b3B2YWwvMiArIDE7ICAgICAgICAgICAvLyBOQVRTOiAodG9wdmFsKzEpCiAgc2l6ZV90IG0gICA9IDI1MDsgICAgICAgICAgICAgICAgICAgIC8vIHByaW50IG91dCBwcmltZXMgaW4gdG9wIDUwMCBvZiByYW5nZQogIHNpemVfdCBjbnQgPSBuOyAgICAgICAgICAgICAgICAgICAgICAvLyBjb3VudCB0aGUgcHJpbWVzCiAKICB2ZWN0b3I8Ym9vbD4gczsgICAvLyA8Y2hhcj4gMnggc2xvd2VyLCBzYW1lIG1lbW9yeSByZXBvcnRlZCBmb3IgMTAwTSB0ZXN0IHJ1bgogIHMucmVzaXplKG4sIHRydWUpOyAgICAgICAgICAgICAgICAgICAvLyBhbGwgcG90ZW50aWFsIHByaW1lcyBhcmUgT04KICAKICBzaXplX3QgaXRvcCA9IGNlaWwoIChzcXJ0KDIqbisxKS0xKS8yICk7IC8vIG1hcmsgb2ZmIG11bHRpcGxlcyBvZiBmaXJzdCBwcmltZXMgdXB0byBzcXJ0CiAgCiAgZm9yKCBzaXplX3QgaT0xOyBpIDw9IGl0b3A7ICsraSApICAgIC8vIEk9Myw1Li4gLCBJPTJpKzEsIGk9MSwyLi4KICB7CiAgICBpZiggc1tpXSApICAgICAgICAgICAgICAgICAgICAgICAgIC8vIEkqSSAtMSAvMiA9IDRpXjIrNGkrMSAtMSAvMiA9IDJpKGkrMSkKICAgICAgZm9yKCBzaXplX3Qgaj0yKmkqKGkrMSk7IGo8bjsgaiArPSBpK2krMSApICAgLy8gSSpJLCArMkksICs0SSwgLi4uCiAgICAgICAgaWYoIHNbal0gKSAgICAgICAgICAgICAgICAgICAgIAogICAgICAgIHsgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgIHNbal0gPSBmYWxzZTsgICAgICAgICAgICAgICAgLy8gbWFyayB0aGUgY29tcG9zaXRlcyBPRkYKICAgICAgICAgIC0tY250OwogICAgICAgIH0KICB9CiAKICBpZiggMiA8PSB0b3B2YWwgJiYgbiA8PSBtICkgICAgICAgICAgLy8gMiBpcyBhIGZpcnN0IHByaW1lIAogICAgICBjb3V0IDw8IDI7CiAgCiAgZm9yKCBzaXplX3Qgaz0obj5tP24tbToxKSwgYz0wOyAgICAgIC8vIHByaW50IG91dCBzb21lIGxhc3QgcHJpbWVzIAogICAgICAgIGsgPCBuOyArK2sgKSAKICAgIGlmKCBzW2tdICkgICAgICAgICAgICAgICAgICAgCiAgICB7CiAgICAgIGNvdXQgPDwgIiAiIDw8IDIqayArIDE7CiAgICAgIGlmKCAoKytjICUgOCkgPT0gMCkgCiAgICAgICAgY291dCA8PCBlbmRsOwogICAgfQogIAogIGNvdXQgPDwgZW5kbCAgCiAgICAgICA8PCBjbnQgIDw8ICIgcHJpbWVzIGZvdW5kLiIgPDwgZW5kbDsKCiAgcmV0dXJuIDA7Cn0=

cmVydW4gdG8gc2VlIHRoZSBjdXJyZW50IHNwZWVkIG9mIElkZW9uZQoyMDE4LTAyLTI1OiA3NU0gcHJpbWVzOiA1LjY3cyAgMTAwLjU2TTogNy45NnMgfm5eMS4xNiAgCgoyMDE4LTAzLTExOiAKIDFlOSBsaW1pdCwgOTk5LDk5OSw5MzcgbGFyZ2VzdCBwcmltZSwgNTAsODQ3LDUzNCBwcmltZXMgZm91bmQgaW4gMy43NXMuCiAyLjA1ZTkgbGltaXQsIDIsMDQ5LDk5OSw5NzkgbGFyZ2VzdCBwcmltZSwgMTAwLDU1NiwzOTMgcHJpbWVzIGZvdW5kIGluIDcuOTNzLCAgIH5uXjEuMTAgLCBOXjEuMDQKCjIwMjItMDgtMjY6IE49MTBeOTogNC4yNy4uNC41OHMgKGhhZCBnb3R0ZW4gc2xvd2VyKQotLS0KMjAxNi0xMC0yMzoKeWVzLCBpdCBnb3QgMC42OC8wLjIzID0gMyB0aW1lcyBmYXN0ZXIhIChmb3IgdGhlIDEwMCBtaWxsaW9uKQoKKG9ubHkgOS40NS83LjQgPSAxLjN4IGZhc3RlciBmb3IgdGhlIDEgYmlsbGlvbiAtLSBwcm9iYWJseSBiZWNhdXNlCiAgICBpdCdzIGEgY29udGlndW91cyBhcnJheSwgc28gY2FjaGUgbG9jYWxpdHkgaXMgYnVzdGVkCiAgICBzZWdtZW50ZWQgc2lldmUgbGlrZWx5IHRvIGdldCB0aGUgZnVsbCBzcGVlZHVwKQ==

rerun to see the current speed of Ideone
2018-02-25: 75M primes: 5.67s  100.56M: 7.96s ~n^1.16  

2018-03-11: 
 1e9 limit, 999,999,937 largest prime, 50,847,534 primes found in 3.75s.
 2.05e9 limit, 2,049,999,979 largest prime, 100,556,393 primes found in 7.93s,   ~n^1.10 , N^1.04

2022-08-26: N=10^9: 4.27..4.58s (had gotten slower)
---
2016-10-23:
yes, it got 0.68/0.23 = 3 times faster! (for the 100 million)

(only 9.45/7.4 = 1.3x faster for the 1 billion -- probably because
    it's a contiguous array, so cache locality is busted
    segmented sieve likely to get the full speedup)