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