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

   call to List.exists returns true as soon as it finds an element of
   ms that divides l, only returning false if no element of ms divides
   l *)

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 list

   if n >= 0, then prs n returns the first n prime numbers, listed in
   descending order

   not tail recursive; in each recursive call, n goes down by 1

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

fun prs 0 = nil
  | prs 1 = [2]
  | prs n =
      let val ms = prs(n - 1)
      in next(ms, hd ms + 1) :: ms 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 = rev(prs n)