fork(1) download
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector> // much better than bitset: see Tw7DO
  4.  
  5. using namespace std;
  6.  
  7. int main() // sieve of Eratosthenes, upto a value,
  8. { // on one contiguous array, as vector<bool>, for ODDS ONLY
  9. const size_t topval = // 541; // C++ // haskell:
  10. // primes upto N in value vector<bool> roll/gaps/Wh ARR/Odds STUArray/Odds
  11. // FaPOB (this) Ojq01 RzqLP KwZNc
  12. // 7919; // 1,000:
  13. // 1000003; // 78,499: 0.04 4.8
  14. // 1299709; // 100,000:
  15. // 2750159; // 200,000: 0.09 4.8
  16. // 5800079; // 400,000: 0.21 5.8
  17. // 15485863; // 1 mln: 0.06s-2.7MB 1.38s 4.7MB 0.67 7.8 0.43 4.8
  18. // 32452843; // 2 mln: 0.16s-2.7MB 3.25s 4.7MB 2.16 11.9 0.98 5.8
  19. // 49979687; // 3 mln: 0.29s-2.7MB 5.40s 4.7MB
  20. // 67867967; // 4 mln: 0.47s-2.7MB 7.68s 4.7MB 5.63 24.2 2.31 8.9
  21. // 86028121; // 5 mln: 0.63s-2.7MB 10.08s 4.7MB 3.04 9.9
  22. // 104395301; // 6 mln: 0.79s-2.7MB 12.66s 4.7MB 9.84 39.6 3.79 10.9
  23. // 113648393; // 6.5 mln: 0.86s-2.7MB 4.14 10.9
  24. // 122949823; // 7 mln: 12.20 36.5
  25. // 133000999; // 7538613: 1.04s-2.7MB 4.95 11.9
  26. // 141650939; // 8 mln: 1.11s-2.7MB 14.61 40.6 5.32 13.0
  27. // 334214459; // 18 mln: 2.89s-2.7MB 13.65 24.2
  28. // 1000000007; // 50,847,535: 9.45s-2.7MB
  29. // 1500000101; // 74,726,535: 14.55s-2.7MB
  30. // 1505800000; // 75,001,089: 14.74s-2.7MB
  31. // 1505776939; // 75 mln 14.61s-2,7MB
  32. // 3 - 6 - 18 - 50 - 74 million primes:
  33. // ~ n^ 1.45 1.18 1.14 1.12 empirical orders of growth
  34. 20000000; // 1,270,607 primes: 0.09s-3.3M (new ideone engine, 2014-01-04)
  35. // 32452843; // 2 mln primes: 0.17s-3.3M
  36.  
  37. size_t n = topval/2 + 1; // NATS: (topval+1)
  38. size_t m = 250; // print out primes in top 500 of range
  39. size_t cnt = n; // count the primes
  40.  
  41. vector<bool> s;
  42. s.resize(n, true); // all potential primes are ON
  43.  
  44. size_t itop = ceil( (sqrt(2*n+1)-1)/2 ); // mark off multiples of first primes upto sqrt
  45.  
  46. for( size_t i=1; i <= itop; ++i ) // I=3,5.. , I=2i+1, i=1,2..
  47. {
  48. if( s[i] ) // I*I -1 /2 = 4i^2+4i+1 -1 /2 = 2i(i+1)
  49. for( size_t j=2*i*(i+1); j<n; j += i+i+1 ) // I*I, +2I, +4I, ...
  50. if( s[j] )
  51. {
  52. s[j] = false; // mark the composites OFF
  53. --cnt;
  54. }
  55. }
  56.  
  57. if( 2 <= topval && n <= m ) // 2 is a first prime
  58. cout << 2;
  59.  
  60. for( size_t k=(n>m?n-m:1), c=0; // print out some last primes
  61. k < n; ++k )
  62. if( s[k] )
  63. {
  64. cout << " " << 2*k + 1;
  65. if( (++c % 8) == 0)
  66. cout << endl;
  67. }
  68.  
  69. cout << endl
  70. << cnt << " primes found." << endl;
  71.  
  72. return 0;
  73. }
  74.  
Success #stdin #stdout 0.09s 3300KB
stdin
Standard input is empty
stdout
 19999519 19999537 19999543 19999547 19999549 19999583 19999631 19999663
 19999697 19999729 19999739 19999789 19999817 19999831 19999843 19999873
 19999891 19999897 19999909 19999927 19999963 19999981 19999999
1270607 primes found.