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

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

primes :: () -> [Int]
primes () = 2: primes'   -- Segmented Generation w/ rem filtering
 where
   primes' = 3: sieve primes' 3 0
   sieve (p:ps) x k =
     let
         q  = p*p
         fs = take k primes'
     in
        [n | n<-[x+2,x+4..q-2], and [rem n f/=0 | f<-fs]]
        ++ sieve ps q (k+1)

{-
postponed filters:                O(n^)          delta  O(n^)
     1,000:       7,919    0.00s          3.7MB   0.0
    30,000:     350,377    0.16s          5.8MB   2.1
   100,000:   1,299,709    0.92s  1.45    9.9MB   6.2   0.90
   300,000:   4,256,233    4.60s  1.46   21.1MB  17.4   0.94
   600,000:   8,960,453   13.27s  1.50   38.5MB  34.8   1.00
 
segmented generation/filtering:   O(n^)          delta  O(n^)
     1,000:       7,919    0.00s          3.7MB   0.0   
    30,000:     350,377    0.09s          4.7MB   1.0   
   100,000:   1,299,709    0.51s  1.44    5.8MB   2.1   0.62
   300,000:   4,256,233    2.49s  1.44   12.9MB   9.2   1.34  0.92
   600,000:   8,960,453    6.77s  1.44   21.1MB  17.4   0.92  1.20  0.95
 1,000,000:  15,485,863   14.09s  1.43   38.5MB  34.8   1.36  0.91  1.20  1.0
-}