Sieve of Eratosthenes: Difference between revisions

=== Another functional version ===

<syntaxhighlight lang="ocaml">

let sieve limit =

let p = Array.make (limit + 1) true in

let rec sieve_outer limit p d =

if d * d > limit then p

else if p.(d) then let p =

let rec sieve_inner limit p m =

if m > limit then p

else sieve_inner limit (p.(m) <- false; p) (m + d)

in sieve_inner limit p (d * d)

in sieve_outer limit p (d + 1)

else sieve_outer limit p (d + 1)

in sieve_outer limit p 2

let primes limit =

let s = (sieve limit) in

List.init (limit - 1) (fun i -> i + 2)

|> List.filter (fun x -> s.(x))</syntaxhighlight>

In the top-level:

<syntaxhighlight lang="ocaml"># primes 200;;

- : int list =

[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; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151; 157; 163; 167; 173; 179; 181; 191; 193; 197; 199]

</syntaxhighlight>