sieve.ml

(* 指定されたリストから指定された数の倍数をとりのぞく *)
(* ignore_multiple : int -> int list -> int list *)
let rec ignore_multiple n ns =
  match ns with
    []      -> []
  | m :: ms -> if m mod n = 0
                   then      ignore_multiple n ms
                   else m :: ignore_multiple n ms

(* range : int -> int list *)
let range n m =
  let rec go i =
    if i = m then i :: []
             else i :: go (i + 1)
  in go n

(* エラトステネスの篩 *)
(* sieve : int -> int list *)
let sieve n =
  let rec go primes ns =
    match ns with
      []      -> primes
    | m :: ms -> go (primes @ [m]) (ignore_multiple m ms)
  in go [] (range 2 n)

let test1 = sieve  10 = [2; 3; 5; 7]
let test2 = sieve 100 = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83; 89; 97]