language: C++ 4.7.2 (gcc-4.7.2)
date: 599 days 1 hour ago
link:
visibility: private 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#include <iostream>
#include <cmath>
#include <vector>  // much better than bitset: see Tw7DO
 
using namespace std;
 
int main()  // sieve of Eratosthenes, upto a value, 
{           // on one whole array, using STL's BITSET, on ODDS
  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: O(n^1.45,1.18,1.14,1.12)
 
  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;
  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;
}