fork(6) 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, **** OLD TIMINGS ****
  8. { // on one contiguous array, as vector<bool>,
  9. // for ODDS ONLY
  10. const size_t topval = // 541; // C++ // haskell:
  11. // primes upto N in value vector<bool> roll/gaps/Wh ARR/Odds STUArray/Odds
  12. // FaPOB (this) Ojq01 RzqLP KwZNc
  13. // 7919; // 1,000:
  14. // 1000003; // 78,499: 0.04 4.8
  15. // 1299709; // 100,000:
  16. // 2750159; // 200,000: 0.09 4.8
  17. // 5800079; // 400,000: 0.21 5.8
  18. // 15485863; // 1 mln: 0.06s-2.7MB 1.38s 4.7MB 0.67 7.8 0.43 4.8
  19. // 32452843; // 2 mln: 0.16s-2.7MB 3.25s 4.7MB 2.16 11.9 0.98 5.8
  20. // 49979687; // 3 mln: 0.29s-2.7MB 5.40s 4.7MB
  21. // 67867967; // 4 mln: 0.47s-2.7MB 7.68s 4.7MB 5.63 24.2 2.31 8.9
  22. // 86028121; // 5 mln: 0.63s-2.7MB 10.08s 4.7MB 3.04 9.9
  23. // 104395301; // 6 mln: 0.79s-2.7MB 12.66s 4.7MB 9.84 39.6 3.79 10.9
  24. // 113648393; // 6.5 mln: 0.86s-2.7MB 4.14 10.9
  25. // 122949823; // 7 mln: 12.20 36.5
  26. // 133000999; // 7538613: 1.04s-2.7MB 4.95 11.9
  27. // 141650939; // 8 mln: 1.11s-2.7MB 14.61 40.6 5.32 13.0
  28. // 334214459; // 18 mln: 2.89s-2.7MB 13.65 24.2
  29. // 1000000007; // 50,847,535: 9.45s-2.7MB
  30. // 1500000101; // 74,726,535: 14.55s-2.7MB
  31. // 1505800000; // 75,001,089: 14.74s-2.7MB
  32. // 1505776939; // 75 mln 14.61s-2,7MB
  33. // 3 - 6 - 18 - 50 - 74 million primes:
  34. // ~ n^ 1.45 1.18 1.14 1.12 empirical orders of growth
  35. // 20000000; // 1,270,607 primes: 0.09s-3.3M (new ideone engine, 2014-01-04)
  36.  
  37. // 75 mln primes: 5.67s **** 2018-02-25 TIMINGS ****
  38. 2050000000; // 100556393 primes: 7.96s ~n^1.16
  39. // 1000000000; // ~N^1.10
  40.  
  41. size_t n = topval/2 + 1; // NATS: (topval+1)
  42. size_t m = 250; // print out primes in top 500 of range
  43. size_t cnt = n; // count the primes
  44.  
  45. vector<bool> s; // <char> 2x slower, same memory reported for 100M test run
  46. s.resize(n, true); // all potential primes are ON
  47.  
  48. size_t itop = ceil( (sqrt(2*n+1)-1)/2 ); // mark off multiples of first primes upto sqrt
  49.  
  50. for( size_t i=1; i <= itop; ++i ) // I=3,5.. , I=2i+1, i=1,2..
  51. {
  52. if( s[i] ) // I*I -1 /2 = 4i^2+4i+1 -1 /2 = 2i(i+1)
  53. for( size_t j=2*i*(i+1); j<n; j += i+i+1 ) // I*I, +2I, +4I, ...
  54. if( s[j] )
  55. {
  56. s[j] = false; // mark the composites OFF
  57. --cnt;
  58. }
  59. }
  60.  
  61. if( 2 <= topval && n <= m ) // 2 is a first prime
  62. cout << 2;
  63.  
  64. for( size_t k=(n>m?n-m:1), c=0; // print out some last primes
  65. k < n; ++k )
  66. if( s[k] )
  67. {
  68. cout << " " << 2*k + 1;
  69. if( (++c % 8) == 0)
  70. cout << endl;
  71. }
  72.  
  73. cout << endl
  74. << cnt << " primes found." << endl;
  75.  
  76. return 0;
  77. }
Success #stdin #stdout 7.96s 127848KB
stdin
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

---
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)
stdout
 2049999503 2049999559 2049999563 2049999569 2049999599 2049999607 2049999613 2049999641
 2049999659 2049999671 2049999697 2049999701 2049999709 2049999751 2049999761 2049999767
 2049999769 2049999793 2049999803 2049999811 2049999817 2049999823 2049999841 2049999881
 2049999883 2049999907 2049999953 2049999967 2049999979
100556393 primes found.