{-# OPTIONS_GHC -O2 -fno-cse #-}

module Main where

main = do
  m <- getLine
  putStr $ m ++ "-th prime: "
  print $ tmwprimes !! (read m - 1)

tmwprimes :: [Int]
tmwprimes = 2:3:5:7:primes'   -- tree-merged | primes-multiples removal
   where                     --             | with 2-3-5-7 WHEEL
    primes'  = roll 11 wheel `minus` (fst.tfold unionSP)
                 [([p*p],[p*q|q<-rollFrom p]) | p <- primes_]
    primes_  = h ++ t `minus` (fst.tfold unionSP)
                 [([p*p],[p*q|q<-rollFrom p]) | p <- primes_]
      where (h,t) = splitAt 6 (11:rollFrom 11)          -- avoid sharing
    
    tfold f xs = go (pairs xs)
      where go (a:b:c:ys) = f a (f b c) `f` go (pairs ys)
            pairs (a:b:ys) = f a b : pairs ys

    unionSP (a:as,bs)   v   = (a:x,y)  where (x,y)=unionSP (as,bs) v
    unionSP u@([],b:bs) v@(c:cs,ds) = case compare b c of
                       LT ->  (b:x,y)  where (x,y)=unionSP ([],bs) v 
                       EQ ->  (b:x,y)  where (x,y)=unionSP ([],bs) (cs,ds) 
                       GT ->  (c:x,y)  where (x,y)=unionSP u       (cs,ds)
    unionSP ([],bs) ([],ds) = ([] ,union bs ds)
    
    rollFrom n = go wheelNums wheel
      where m = (n-11) `mod` 210
            go (x:xs) (w:ws) | x==m = roll (n+w) ws 
                             | True = go xs ws
    wheelNums  = roll 0 wheel         -- [0,2,6,8,12,18, ...] 
    roll       = scanl (+)
    wheel      = 2:4:2:4:6:2:6:4:2:4:6:6:2:6:4:2:6:4:6:8:4:2:4:2:
                 4:8:6:4:6:2:4:6:2:6:6:4:2:4:6:2:6:4:2:4:2:10:2:10:wheel
    
    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        b        = if null a then b else a
    
    minus a@(x:xs) b@(y:ys) = case compare x y of 
                                LT -> x: xs `minus` b
                                EQ ->    xs `minus` ys
                                GT ->    a  `minus` ys
    minus a        b        = a