Misc.ml

let rec range a b = 
  if a > b then [] 
  else a :: range (succ a) b
;;

(*
  filter that corresponding to the tail recursion optimization.
  standard List.filer isn't tailrec.
*)
let rec tailrec_filter p = function
  | []  -> []
  | a :: r -> if p a then a :: tailrec_filter p r else tailrec_filter p r
;;

let sieve max =
  	let rec filter_again = function
  	| [] -> []
  	| n :: r as l ->
  		if n * n > max then l else n :: filter_again (tailrec_filter (fun x -> x mod n <> 0) r)
  	in
  	filter_again (range 2 max)
;;