home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 4 / Apprentice-Release4.iso / Languages / Caml Light 0.7 / examples / basics / sieve.ml < prev    next >
Encoding:
Text File  |  1995-06-01  |  1.2 KB  |  55 lines  |  [TEXT/MPS ]
  1. (* Eratosthene's sieve *)
  2.  
  3. (* interval min max = [min; min+1; ...; max-1; max] *)
  4.  
  5. let rec interval min max =
  6.   if min > max then [] else min :: interval (succ min) max
  7. ;;
  8.  
  9. (* filter p L returns the list of the elements in list L
  10.    that satisfy predicate p *)
  11.  
  12. let rec filter p = function
  13.      []  -> []
  14.   | a::r -> if p a then a :: filter p r else filter p r
  15. ;;
  16.  
  17. (* Application: removing all numbers multiple of n from a list of integers *)
  18.  
  19. let remove_multiples_of n =
  20.   filter (fun m -> m mod n <> 0)
  21. ;;
  22.  
  23. (* The sieve itself *)
  24.  
  25. let sieve max =
  26.   let rec filter_again = function
  27.      [] -> []
  28.   | n::r as l ->
  29.       if n*n > max then l else n :: filter_again (remove_multiples_of n r)
  30.   in
  31.     filter_again (interval 2 max)
  32. ;;
  33.  
  34. (* The entry point *)
  35.  
  36. let usage() =
  37.   print_string "Usage: sieve <n>\n";
  38.   exit 2
  39. ;;
  40.  
  41. if sys__interactive then () else
  42. if vect_length sys__command_line <> 2 then begin
  43.   print_string "Usage: sieve <n>";
  44.   print_newline()
  45. end else begin
  46.   try
  47.     let n = int_of_string sys__command_line.(1) in
  48.     do_list (fun n -> print_int n; print_string " ") (sieve n);
  49.     print_newline()
  50.   with Failure "int_of_string" ->
  51.     print_string "Bad integer constant";
  52.     print_newline()
  53. end
  54. ;;
  55.