{-# OPTIONS_GHC -O2 #-}

module Main where

import Data.Array.Unboxed

main = do
  m <- getLine
  print {- $ fork(last,length) -} $ primesToAO (read m)

-- the simplest Sieve of Eratosthenes formulation, using
-- an array that is passed as an accumulating argument
-- between steps of iterative computation, and as such
-- (could be, but ain't) liable to the destructive update (but is fast, still, 
-- on unboxed arrays, with explicit type signature)

primesToA :: Int -> [Int]
primesToA m | m > 2 = sieve 3 (array (3,m)  [(i,odd i) | i<-[3..m]]     -- 16M:2.03s
                                 -- (zip [3..m] $ cycle [True,False])     -- 16M:2.90s
                                 :: UArray Int Bool)
  where
    sieve p a 
      | p*p > m   = 2 : [i | (i,True) <- assocs a]
      | a!p       = sieve (p+2) $ a//[(i,False) | i <- [p*p, p*p+2*p..m]]
      | otherwise = sieve (p+2) a


fork (f,g) x = (f x,g x)  -- f &&& g


-- apply the simple optimization of working with odds only: --------

primesToAO :: Int -> (Int,Int)
primesToAO m | m > 2 = sieve 3 (-- array (1,m1)  [(i,True) | i<-[1..m1]]    -- 16M 0.73s-7.8MB
                                accumArray const True (1,m1) []             -- 16M 0.68s-7.8MB
                                  :: UArray Int Bool)
  where
    m1 = (m-1) `div` 2
    r  = floor . sqrt $ fromIntegral m + 1
    sieve p a 
      | p > r     = let
                      last = head [i | i<-[u,u-1..l], a!i]               -- plug
                      len  = length [() | (i,True) <- assocs a]           --  the leak
                      (l,u) = bounds a
                    in   (last*2+1, len+1)                                -- '2' is prime too
      | a!p1      = sieve (p+2) $ a//[(i,False) | i <- [q1, q1+p..m1]]
      | otherwise = sieve (p+2) a
                       where p1 = (p-1) `div` 2
                             q1 = (p*p-1) `div` 2

{-
 en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number

 n(log n + log(log n) - 1) < p_n <  n(log n + log(log n))  , for n >= 6

aaprimes n = 
  let x=fromIntegral n
      a=primesToA $ ceiling $ x*(log x + log(log x))   -- good for n >= 4  (p >= 7)
      (l,u)=bounds a
      p=head [i | i<-[u,u-1..l], a!i]
      len=length [() | (i,True) <- assocs a]
      ..........


         m     n      Data.Array           Data.Array.Unboxed                             Odds_Only
                                                                      Theoretical
100k  (99991,9592)    0.13s-6.8MB           0.02s-4.8MB                  cpxty
200k  (199999,17984)  0.39s-9.9MB   n^1.75  0.03s-4.8MB            n*log n*log(log n)
400k  (399989,33860)  1.06s-26.3MB  n^1.58  0.04s-4.8MB                              
1M    (999983,78498)  3.99s-45.7MB  n^1.58  0.09s-5.8MB                            0.04s-4.8MB
2M    (1999993,148933) 11.46s-84.6  n^1.65  0.16s-7.8MB    n^0.90-1.72   n^1.122   0.07s-4.8MB
4M    (3999971,283146)                      0.34s-9.9MB    n^1.17-0.83   n^1.114   0.14s-5.8MB   n^1.08
8M    (7999993,539777)                      0.73s-18.1MB   n^1.18-1.49   n^1.108   0.31s-5.8MB   n^1.23
16M  (15999989,1031130)                     2.03s-27.3MB   n^1.58-0.81             0.68s-7.8MB   n^1.21
32M  (31999939,1973815)                     4.89s-84.6MB   n^1.35-1.95             2.13s-11.9MB  n^1.76-1.33
50M  (49999991,3001134)                     8.45s-115.3MB  n^1.31-0.78             3.81s-16.0MB  n^1.39-1.09
64M  (63999979,3785086)                                                            5.24s-20.1MB  n^1.37-1.34
100M (99999989,5761455)                                                            9.27s-28.3MB  n^1.36-1.02
104M (104395301,6000000)                                                           9.80s-39.6MB -}