Did you try using simple datastructure first before jumping on the sophisticated ones?
On my machine, the following code is only 4x slower than you C++ version (note that I made the minimal changes to use an Array as the cache, and a list to accumulate results; you could use the array get/set syntactic sugar):
let find_primes n =
let is_prime = Array.make (n + 1) true in
let last = int_of_float (sqrt (float n)) in
for i = 2 to last do
if not (Array.get is_prime i) then () else begin
let j = ref (i * i) in
while !j <= n; do
Array.set is_prime !j false;
j := !j + i;
done;
end;
done;
let ar = ref [] in
for i = 2 to n do
if Array.get is_prime i then ar := i :: !ar else ()
done;
ar
(4x slower: it takes 4s to compute the 10_000_000 first primes, vs. 1s for g++ -O1 or -O2 on your code)
Realizing that the efficiency of your bitvector solution probably comes from the economic memory layout, I changed the code to use strings instead of arrays:
let find_primes n =
let is_prime = String.make (n + 1) '0' in
let last = int_of_float (sqrt (float n)) in
for i = 2 to last do
if not (String.get is_prime i = '0') then () else begin
let j = ref (i * i) in
while !j <= n; do
String.set is_prime !j '1';
j := !j + i;
done;
end;
done;
let ar = ref [] in
for i = 2 to n do
if String.get is_prime i = '0' then ar := i :: !ar else ()
done;
ar
This now takes only 2s, which makes it 2x slower than your C++ solution.