//
//   1000 이하의 소수를 구하는 프로그램
//
//   by Oukseh Lee 

// gen a b: [a, ..., b] 리스트를 생성한다. 

fun gen a b =
  if a > b then
    []
  else
    a :: gen (a+1) b

// filter f l: 리스트 l의 원소 x중 f(x)=true 인 것만 고른다
//             이 함수를 작성하지 않고 List.filter 를 써도 된다. 

fun filter f l =
  case l of
    []   => []
  | h::t => if f h then
              h :: filter f t
            else
              filter f t

// [2, ..., n] 리스트를 만들고
// 앞에서부터 머리값 h로 나누어 지는 것들을 하나씩 지워나간다.
// 단, h*h 가 n 보다 커지는 h 이후에는 할 필요없다. 

fun sieve n =
  let fun loop l =
        case l of
          []   => []
        | h::t => if h*h > n then
                    l
                  else
                    h :: loop (filter (fn x => x % h <> 0) t)
  in  loop (gen 2 n)
  end

// sieve 1000 을 돌리고 출력한다. 

val _ = List.iter (fn x => print_int x; print_newline())
                  (sieve 1000)