2015-08-06

Upto 1 Billion value of primes generated within 5 seconds

Revised date: 2015-09-10

• Not initialized flag bug fixed.
• Not checked value of lmt pointed by sqrt bug fixed.

Added g++ O2 option that got faster result within 5 seconds.

Many programming contest participants are using this bitwise version of Eratosthenes Sieve. This is very fast.

It has resulted upto 1 Billion value of primes generated within 5 seconds on our windows vm on vcpu 8(Xeon E3-1245) kvm. Build and run by gcc with MSYS.

Description describes below web site.

I, ME AND MYSELF !!!: Segmented Sieve

Non segmented version

sieve.cpp

```c++
#include <iostream>
#include <chrono>
#include <cmath>
#include <vector>
#include <memory>
using namespace std;
#include <stdint.h>
typedef uint32_t U32;
typedef uint64_t U64;

#define chkC(n) (pflag[n>>6]&(1<<((n>>1)&31)))
#define setC(n) (pflag[n>>6]|=(1<<((n>>1)&31)))

shared_ptr<vector<U64> > sieve(U64 n) {
  auto pprimes = make_shared<vector<U64> >(50847534L);
  vector<U64> &primes = *pprimes.get();
  U32 *pflag = (U32*)calloc(n / 64 + 1, sizeof(U32));

  U64 lmt = sqrt(n);
  U64 i, j, k;
  for (i=3; i<=lmt; i += 2) {
    if (!chkC(i)) {
      for (j=i*i, k=i<<1; j<n; j+=k) {
        setC(j);
      }
    }
  }
  primes[(j=0)++] = 2;
  for (i=3; i<n; i += 2) {
    if (!chkC(i)) {
      primes[j++] = i;
    }
  }
  primes.resize(j);
  free(pflag);
  return pprimes;
}

int main() {
  const auto startTime = chrono::system_clock::now();
  auto pprimes = sieve(1000000000L);
  const auto endTime = chrono::system_clock::now();
  const auto timeSpan = endTime - startTime;
  vector<U64>& primes = *pprimes.get();
  U32 len = primes.size();
  cout << "Prime count=" << len << ", last value=" << primes[len-1] << endl;
  cout << "Elapsed: "
    << chrono::duration_cast<chrono::milliseconds>(timeSpan)
    .count() << " ms" << endl;
  return 0;
}

Build

$ g++ -o sieve sieve.cpp -std=c++11 -O2

Run

$ ./sieve
Prime count=50847534, last value=999999937
Elapsed: 4849 ms