(* primes.sml *)

(* val divisible : int * int list -> bool

   if ms is an ascending sequence of primes with no gaps, and, if ms
   <> [], then l is not divisible by any primes < hd ms, and l is >
   the last element of ms, then divisible(l, ms) tests whether l is
   divisible by an element of ms

   it returns true as soon as the next element divides l; otherwise it
   returns false if the square of that next element is > l

   tail recursive, using tail of second argument *)

fun divisible(_, nil)     = false
  | divisible(l, m :: ms) =
      l mod m = 0 orelse
      (m * m < l andalso divisible(l, ms))

(* val next : int list * int -> int

   if l >= 3 and ms is all the primes < l in ascending order, then
   next(ms, l) returns the smallest prime >= l (we know such a prime
   exists)

   tail recursive; in each recursive call, the distance between the
   second argument and the smallest prime >= the second argument goes
   down *)

fun next(ms, l) =
      if divisible(l, ms)
      then next(ms, l + 1)
      else l

(* val prs : int * int * int list * int -> int list

   if 1 <= i <= n, ms is the first i primes, listed in ascending
   order, and m is the last element of ms, then prs(n, i, ms, m)
   returns the first n primes, listed in ascending order

   tail recursive, with n - i decreasing; second argument of calls to
   next in optimal order

   but each tail-recursive call involves an inefficient append *)

fun prs(n, i, ms, m) =
      if i = n
      then ms
      else let val k = next(ms, m + 1)
           in prs(n, i + 1, ms @ [k], k) end

(* val primes : int -> int list

   if n >= 0, then primes n returns the first n prime numbers,
   listed in ascending order *)

fun primes n = if n = 0 then nil else prs(n, 1, [2], 2)