test/sieve.ml

   1 (***********************************************************************)
   2 (*                                                                     *)
   3 (*                           Objective Caml                            *)
   4 (*                                                                     *)
   5 (*            Xavier Leroy, projet Cristal, INRIA Rocquencourt         *)
   6 (*                                                                     *)
   7 (*  Copyright 1996 Institut National de Recherche en Informatique et   *)
   8 (*  en Automatique.  All rights reserved.  This file is distributed    *)
   9 (*  under the terms of the Q Public License version 1.0.               *)
  10 (*                                                                     *)
  11 (***********************************************************************)
  12
  13 (* $Id$ *)
  14
  15 (* Eratosthene's sieve *)
  16
  17 (* interval min max = [min; min+1; ...; max-1; max] *)
  18
  19 let rec interval min max =
  20   if min > max then [] else min :: interval (min + 1) max
  21
  22
  23 (* filter p L returns the list of the elements in list L
  24    that satisfy predicate p *)
  25
  26 let rec filter p = function
  27      []  -> []
  28   | a::r -> if p a then a :: filter p r else filter p r
  29
  30
  31 (* Application: removing all numbers multiple of n from a list of integers *)
  32
  33 let remove_multiples_of n =
  34   filter (fun m -> m mod n <> 0)
  35
  36
  37 (* The sieve itself *)
  38
  39 let sieve max =
  40   let rec filter_again = function
  41      [] -> []
  42   | n::r as l ->
  43       if n*n > max then l else n :: filter_again (remove_multiples_of n r)
  44   in
  45     filter_again (interval 2 max)
  46
  47
  48 let rec do_list f = function
  49     [] -> ()
  50   | a::l -> f a; do_list f l
  51
  52
  53 let _ =
  54   do_list (fun n -> print_int n; print_string " ") (sieve 50000);
  55   print_newline();
  56   exit 0