ACM International Collegiate Programming Contest, Asia Regional (Tokyo), 2007, Problem B

gistfile1.sml

exception NotFoundException

fun get_primes n =
    let
        val l = List.tabulate (n, fn n => n + 2)
        fun get_primes_sub nil result = result
          | get_primes_sub (x::xs) result = 
            get_primes_sub (List.filter (fn n => n mod x <> 0) xs) (x::result)
    in
        List.rev (get_primes_sub l nil)
    end

fun solve_one n primes ppairs =
    case List.find (fn x => x = n) primes of
        SOME x => x
      | NONE => case List.find (fn (p, q) => p <= n andalso n < q) ppairs of
                    SOME (p, q) => q - p
                  | NONE => raise NotFoundException

fun solve file =
    let
        open TextIO
        val primes = get_primes 1299720
        val ppairs = ListPair.zip (primes, tl primes)
        val f = openIn file
        val line = ref NONE
    in
        while (line := inputLine f; !line <> SOME "0\n") do
            let
                val n = Int.fromString (valOf (!line))
            in
                case n of
                    SOME v => 
                    output (stdOut, 
                            Int.toString (solve_one v primes ppairs) ^ "\n")
                  | NONE => raise NotFoundException
            end;
        closeIn f
    end