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