[Shootout-list] C++ sieve using vector<bool>

[Jon Harrop]

I saw a discussion where someone said it would be nice to have a C++ 
implementation of the sieve (sieve-bits?) which used vector<bool>. Indeed, 
this is the obvious way to implement the sieve in C++. I happen to have one 
lying around:

#include <vector>

int sieve(int n) {
  std::vector<bool> t(n+1);
  int count = 0;

  for (int i=2; i<=n; ++i)
    if (! t.at(i)) {
      ++count;
      for (int j=i*2; j<=n; j+=i) t.at(j) = true;
    }

  return count;
}

Hopefully that'll be of some use. :-)

IMHO, this counts as the C++ implementation of both nsieve and nsieve-bits as 
the STL's vector implements arrays and happens to be partially specialised 
for bools. Note that this implementation uses bounds checking.

Also, performance can be improved significantly by reading from the underlying 
array and only writing if the write will change the contents. I believe this 
is because the write-cache doesn't fill as much. This OCaml implementation is 
faster than the one currently on the shootout on my computer (but maybe it 
isn't "legal"):

open Bigarray

let nsieve n =
  let a =  Array1.create int8_unsigned c_layout ((n lsr 3) + 2) in
  Array1.fill a 0xFF;
  let rec clear i j =
    if j <= n then (
      let ic = j lsr 3 in
      let bit = a.{ic} land lnot(1 lsl (j land 0x7)) in
      if a.{ic} <> bit then a.{ic} <- bit;
      clear i (j + i) ) in
  let count = ref 0 in
  for i = 2 to n do
    if a.{i lsr 3} land (1 lsl (i land 0x7)) > 0 then begin
      incr count;
      if i*i <= n then clear i (2*i)
    end
  done;
  !count

let test n =
  let m = (1 lsl n) * 10000 in
  Printf.printf "Primes up to %8i %8i\n" m (nsieve m)

let () =
  let n =
    try int_of_string(Array.get Sys.argv 1)
    with _ -> (Printf.printf "usage: %s N\n" Sys.argv.(0); exit 2) in
  test n;
  if n >= 1 then test(n-1);
  if n >= 2 then test(n-2)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists