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

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

primes :: () -> [Int]
primes () = 2: primes'   -- TREE-folding multiples-union
 where                   --  ERATOSthenes sieve
   primes'  = 3: sieve primes' 5 9 []
   sieve (p:ps) x q fs = 
        ([x,x+2..q-2] `minus` 
                          foldt [[y+s,y+2*s..q] | (s,y) <- fs])
        ++ sieve ps (q+2) (head ps^2)
             ((++ [(2*p,q)]) [(s,q-rem (q-y) s) | (s,y) <- fs])
    
   foldt (a:xs)     = union a (foldt (pairs xs)) 
   foldt []         = []
   pairs (a:b:xs)   = union a b : pairs xs
   pairs xs         = xs
   
   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
   
{-                           FOLDT            (w/ foldr)        (w/ foldl)
   100,000:  1,299,709   0.23s    6.8MB      0.40s   7.8MB      1.33s  8.8MB
   0.5 mln:  7,368,787   1.54s   25.2MB      3.80s  31.3MB    300k:7.35s 19MB
   1.0 mln: 15,485,863   3.65s   48.8MB     10.31s  57.0MB    450k:14.1s 28MB
   2.0 mln: 32,452,843   8.74s  110.2MB  
   2.5 mln: 41,161,739  12.02s  134.8MB
   
                     O(n^1.28)  O(n^1.1)   (n^1.41) (n^1.3)   (n^1.57) (^2.1)
-}