(* primes.sml *)

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

   if l >= 3 and ms is all the primes < l in some order, then next(ms,
   l) returns the smallest prime >= l (we know such a prime exists,
   because there are infinitely many primes)

   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 List.exists (fn m => l mod m = 0) ms
      then next(ms, l + 1)
      else l

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

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

   tail recursive, with n - i decreasing

   but second argument of calls to next in non-optimal order *)

fun prs(n, i, ms) =
      if i = n
      then rev ms
      else prs(n, i + 1, next(ms, hd ms + 1) :: ms)

(* 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])