-- 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

primesToUA :: Word32-> [Word32]
primesToUA top = do
    let sieveUA top = runSTUArray $ do    
        let m = ((fromIntegral top) - 3) `div` 2 :: Int
        buf <- newArray (0,m) True -- :: ST s (STUArray s Int Bool)
        let cullUA i = do
            let p = i + i + 3
                strt = p * (i + 1) + i
            let cull j = do
                if j > m then cullUA (i + 1)
                else do
                    unsafeWrite buf j False
                    cull (j + p)
            if strt > m then return ()
	        else do
	            e <- unsafeRead buf i
	            if e then cull strt else cullUA (i + 1)
        cullUA 0; return buf
    if top > 1 then 2 : [2 * (fromIntegral i) + 3 | (i,True) <- assocs $ sieveUA top]
    else []

main = do 
   x <- read `fmap` getLine      --   1mln    2mln    10mln   100mln
   print (length (primesToUA x))   --   0.01    0.02     0.09     1.26  seconds