Le crible d'Ératosthène

let crible n =
  let est_premier = Array.make (n + 1) true in
  est_premier.(0) <- false;
  if n >= 1 then est_premier.(1) <- false;
  for d = 2 to n do
    if est_premier.(d) then begin
      let m = ref (d * d) in
      while !m <= n do
        est_premier.(!m) <- false;
        m := !m + d
      done
    end
  done;
  est_premier

On part de « tout est premier », on élimine 0 et 1, puis pour chaque d encore marqué premier, on barre tous ses multiples à partir de d*d (les plus petits ont déjà été barrés par des facteurs plus petits). Le tableau de booléens est l'outil idéal : accès et mise à jour en temps constant. (Variant de la boucle while : n - !m, qui décroît de d à chaque tour.)