-- from http://w...content-available-to-author-only...l.org/haskellwiki/Prime_numbers#Using_ST_Array

{-# OPTIONS -O2 -optc-O3 #-}
import Data.Word
import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
import Data.Array.Base

primesUA :: () -> [Word32]
primesUA () = do
    let pgSZBTS = 262144 * 8
    let sieveUA :: (Integral t, Integral t1) => t -> [t1] -> ST s (STUArray s Int Bool)
        sieveUA low bps = do
            let nxt = (fromIntegral low) + (fromIntegral pgSZBTS)
            buf <- newArray (0,pgSZBTS - 1) True :: ST s (STUArray s Int Bool)
            let cullUAbase i = do
                let p = i + i + 3
                    strt = p * (i + 1) + i
                let cull j = do
                    if j >= pgSZBTS then cullUAbase (i + 1)
                    else do
                        unsafeWrite buf j False
                        cull (j + p)
                when (strt < pgSZBTS) $ do
                    e <- unsafeRead buf i
                    if e then cull strt else cullUAbase (i + 1)
            let cullUA ~(p:t) = do
                let bp = (fromIntegral p)
                    i = (bp - 3) `div` 2
                    s = bp * (i + 1) + i
                let cull j = do
                    if j >= pgSZBTS then cullUA t
                    else do
                        unsafeWrite buf j False
                        cull (j + (fromIntegral p))
                when (s < nxt) $ do
                    let strt = do
                        if s >= low then fromIntegral (s - low)
                        else  do
                            let b = (low - s) `rem` bp
                            if b == 0 then 0 else fromIntegral (bp - b)
                    cull strt
            if low <= 0 then cullUAbase 0 else cullUA bps
            return buf
    let sieveList low bps = do
        [2 * ((fromIntegral i) + low) + 3 | (i,True) <- assocs $ runSTUArray $ sieveUA low bps]
    let sieve low bps = do
        (sieveList low bps) ++ sieve (low + (fromIntegral pgSZBTS)) bps
    let primes' = ((sieveList 0 []) ++ sieve (fromIntegral pgSZBTS) primes') :: [Word32]
    2 : sieve 0 primes'

main = do 
   x <- read `fmap` getLine      --   1mln    2mln    10mln   100mln
                                 --   0.02    0.03     0.13     1.13  seconds
   print (length (takeWhile ((>=) (fromIntegral x)) (primesUA ())))