{-# OPTIONS_GHC -O2 #-}
module Main where

main = interact (\s-> show $ primes() !! (read s - 1))

primes :: () -> [Int]
primes () = 2: primes'   -- LINEAR-folding multiples-union 
 where                   --  ERATOSthenes sieve
   primes'  = 3: sieve primes' 3 []
   sieve (p:ps) x fs = 
     let 
         q=p*p 
     in
        ([x+2,x+4..q-2] `minus` 
            foldl union [] [[y+s,y+2*s..q] | (s,y) <- fs])
        ++ sieve ps q 
               ((2*p,q):[(s,q-rem (q-y) s) | (s,y) <- fs])

   union a@(x:xs) b@(y:ys) = case compare x y of 
                                  LT -> x : union xs b 
                                  EQ -> x : union xs ys
                                  GT -> y : union a  ys
   union a        []       = a
   union []       b        = b
 
   minus a@(x:xs) b@(y:ys) = case compare x y of 
                                  LT -> x : minus xs b
                                  EQ ->     minus xs ys
                                  GT ->     minus a  ys
   minus a        b        = a

{-
                            FOLDL             FOLDR 
    50,000:    611,953   0.15s  5.8MB      0.44s   5.8MB
   100,000:  1,299,709   0.41s  7.8MB      1.28s   8.8MB
   200,000:  2,750,159   1.09s 14.0MB      3.83s  14.0MB
   300,000:  4,256,233   1.93s 19.1MB      7.08s  19.1MB
   400,000:  5,800,079   2.95s 25.2MB     11.08s  24.2MB 
   500,000:  7,368,787   3.94s 28.2MB   > 15 sec >30.4MB
 1,000,000: 15,485,863  10.93s 58.0MB   > 15 sec >30.4MB

                     O(n^1.45) O(n^0.9)
-}