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. 100000000;
  36. // 32452843; // 2 mln primes: 0.17s-3.3M
  37.  
  38. size_t n = topval/2 + 1; // NATS: (topval+1)
  39. size_t m = 250; // print out primes in top 500 of range
  40. size_t cnt = n; // count the primes
  41.  
  42. vector<bool> s;
  43. s.resize(n, true); // all potential primes are ON
  44.  
  45. size_t itop = ceil( (sqrt(2*n+1)-1)/2 ); // mark off multiples of first primes upto sqrt
  46.  
  47. for( size_t i=1; i <= itop; ++i ) // I=3,5.. , I=2i+1, i=1,2..
  48. {
  49. if( s[i] ) // I*I -1 /2 = 4i^2+4i+1 -1 /2 = 2i(i+1)
  50. for( size_t j=2*i*(i+1); j<n; j += i+i+1 ) // I*I, +2I, +4I, ...
  51. if( s[j] )
  52. {
  53. s[j] = false; // mark the composites OFF
  54. --cnt;
  55. }
  56. }
  57.  
  58. if( 2 <= topval && n <= m ) // 2 is a first prime
  59. cout << 2;
  60.  
  61. for( size_t k=(n>m?n-m:1), c=0; // print out some last primes
  62. k < n; ++k )
  63. if( s[k] )
  64. {
  65. cout << " " << 2*k + 1;
  66. if( (++c % 8) == 0)
  67. cout << endl;
  68. }
  69.  
  70. cout << endl
  71. << cnt << " primes found." << endl;
  72.  
  73. return 0;
  74. }
  75.  
Success #stdin #stdout 0.68s 3300KB
stdin
Standard input is empty
stdout
 99999509 99999517 99999539 99999541 99999547 99999551 99999563 99999587
 99999589 99999611 99999617 99999623 99999643 99999677 99999703 99999721
 99999773 99999787 99999821 99999827 99999839 99999847 99999931 99999941
 99999959 99999971 99999989
5761455 primes found.