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
|
(***********************************************************************)
(* *)
(* Objective Caml *)
(* *)
(* Pierre Weis, projet Cristal, INRIA Rocquencourt *)
(* *)
(* Copyright 2001 Institut National de Recherche en Informatique et *)
(* en Automatique. All rights reserved. This file is distributed *)
(* only by permission. *)
(* *)
(***********************************************************************)
(* Erathostene sieve, imperative version.
A vector is initialized with consecutive integers.
Then the vector is sieved by removing multiples of the next still
not removed integer, starting from 2. *)
let fixed_bound = 5000000;;
let sieve max =
let v = Array.init max (fun i -> i + 1) in
let prime_count = ref 0 in
v.(0) <- 0;
prime_count := 0;
for i = 1 to max - 1 do
if v.(i) <> 0 then begin
prime_count := !prime_count + 1;
let prime = i + 1 in
let rec sieve j =
if j < max then begin v.(j) <- 0; sieve (j + prime) end in
sieve (i + prime)
end
done;
Printf.printf
"There are %d primes less than or equal to %d.\n" !prime_count max;;
let main () =
let max =
try int_of_string (Sys.argv.(1))
with _ -> fixed_bound in
sieve max;;
main ();;
|
