Prime number sieve in Standard ML
fun buildPrimes ps x =
          if length ps &gt;= n then ps



Don't forget that length is expensive. It's definitely worth using an extra accumulator variable to track either the length or the number of primes left to find. I haven't done proper benchmarks, but it seems to give a speedup of a factor of 2 for input 10000.



I understand why you prepend newly found primes to the list and then reverse it at the end: appending the prime to the end of the list is expensive. But the other side of the argument is that the smaller primes are far more valuable for eliminating composite numbers, and in my testing replacing (x::ps) with (ps @ [x]) and ditching the rev makes a significant improvement to speed.

If performance is a high priority then you could take a hybrid approach which gives you the best of both worlds at the cost of complicating the code: have one list which is sorted in increasing order and another list which is sorted in decreasing order. Use additional accumulator variables to track their lengths. Add new primes to the front of the decreasing list, and when the decreasing list is as long as the increasing list replace them with asc @ (rev desc) and [].



My SML isn't at a level where I feel qualified to say what is idiomatic and what isn't, but one of the most advanced things I studied in SML at university was lazy infinite lists, and I think they have a claim to be fairly idiomatic in functional languages in general. It's not too hard to rework this sieve into a lazy infinite style. We define a type for lazy infinite lists of integers:

datatype stream = Cons of int * (unit -&gt; stream);


where unit is the tuple of length 0, (); then a lazy list of all integers can be built with

fun integers n = Cons(n, fn () =&gt; integers (n + 1));


Filtering an infinite list is useful enough to define it outside the prime generator:

fun filter f (Cons(x,xs)) =
    if f(x) then Cons(x, fn () =&gt; filter f (xs()))
    else filter f (xs());


And then the sieve itself just builds up layers of filters:

val primes =
    let
        fun filter_multiples m = filter (fn i =&gt; i mod m &lt;&gt; 0)
        fun prime_extractor (Cons(p,xs)) = Cons(p, fn () =&gt; prime_extractor (filter_multiples p (xs())))
    in
        prime_extractor (integers 2)
    end;


For testing purposes, converting the first n elements to a normal list is convenient:

fun take 0 (Cons(x, xs)) = []
  | take n (Cons(x, xs)) = x :: (take (n - 1) (xs()));


For production quality this should probably be wrapped in a module, but that's at the level that I've heard of it but don't know any details.