module type STREAM = sig
type t
val start : t
val next : t -> t
val value : t -> int
end
let sift s =
open s as S : STREAM in
let divisor = S.value S.start in
let module Next = struct
type t = S.t
let value = S.value
let rec next x =
let x = S.next x in
if S.value x mod divisor = 0 then next x else x
let start = next (S.start)
end in
pack (Next : STREAM)
module Sieve = struct
type t = [| STREAM |]
let start =
let module Start = struct
type t = int
let start = 2
let next = succ
let value x = x
end in
pack (Start : STREAM)
let next = sift
let value x =
open x as S : STREAM in
S.value S.start
end
open Sieve
let rec nthstate = function
0 -> start
| n -> next (nthstate (n-1))
let nthprime n = value (nthstate n)