fork(6) download
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector> // much better than bitset: see Tw7DO
  4.  
  5. using namespace std; // by stackoverflow.com/users/849891/will-ness
  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 3.74s 15240KB
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
 999999503 999999527 999999541 999999587 999999599 999999607 999999613 999999667
 999999677 999999733 999999739 999999751 999999757 999999761 999999797 999999883
 999999893 999999929 999999937
50847534 primes found.