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

LS0gZnJvbSBodHRwOi8vdy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4ubC5vcmcvaGFza2VsbHdpa2kvUHJpbWVfbnVtYmVycyNVc2luZ19TVF9BcnJheQoKey0jIE9QVElPTlMgLU8yIC1vcHRjLU8zICMtfQppbXBvcnQgRGF0YS5Xb3JkCmltcG9ydCBDb250cm9sLk1vbmFkCmltcG9ydCBDb250cm9sLk1vbmFkLlNUCmltcG9ydCBEYXRhLkFycmF5LlNUCmltcG9ydCBEYXRhLkFycmF5LlVuYm94ZWQKaW1wb3J0IERhdGEuQXJyYXkuQmFzZQoKcHJpbWVzVG9VQSA6OiBXb3JkMzItPiBbV29yZDMyXQpwcmltZXNUb1VBIHRvcCA9IGRvCiAgICBsZXQgc2lldmVVQSB0b3AgPSBydW5TVFVBcnJheSAkIGRvICAgIAogICAgICAgIGxldCBtID0gKChmcm9tSW50ZWdyYWwgdG9wKSAtIDMpIGBkaXZgIDIgOjogSW50CiAgICAgICAgYnVmIDwtIG5ld0FycmF5ICgwLG0pIFRydWUgLS0gOjogU1QgcyAoU1RVQXJyYXkgcyBJbnQgQm9vbCkKICAgICAgICBsZXQgY3VsbFVBIGkgPSBkbwogICAgICAgICAgICBsZXQgcCA9IGkgKyBpICsgMwogICAgICAgICAgICAgICAgc3RydCA9IHAgKiAoaSArIDEpICsgaQogICAgICAgICAgICBsZXQgY3VsbCBqID0gZG8KICAgICAgICAgICAgICAgIGlmIGogPiBtIHRoZW4gY3VsbFVBIChpICsgMSkKICAgICAgICAgICAgICAgIGVsc2UgZG8KICAgICAgICAgICAgICAgICAgICB1bnNhZmVXcml0ZSBidWYgaiBGYWxzZQogICAgICAgICAgICAgICAgICAgIGN1bGwgKGogKyBwKQogICAgICAgICAgICBpZiBzdHJ0ID4gbSB0aGVuIHJldHVybiAoKQoJICAgICAgICBlbHNlIGRvCgkgICAgICAgICAgICBlIDwtIHVuc2FmZVJlYWQgYnVmIGkKCSAgICAgICAgICAgIGlmIGUgdGhlbiBjdWxsIHN0cnQgZWxzZSBjdWxsVUEgKGkgKyAxKQogICAgICAgIGN1bGxVQSAwOyByZXR1cm4gYnVmCiAgICBpZiB0b3AgPiAxIHRoZW4gMiA6IFsyICogKGZyb21JbnRlZ3JhbCBpKSArIDMgfCAoaSxUcnVlKSA8LSBhc3NvY3MgJCBzaWV2ZVVBIHRvcF0KICAgIGVsc2UgW10KCm1haW4gPSBkbyAKICAgeCA8LSByZWFkIGBmbWFwYCBnZXRMaW5lICAgICAgLS0gICAxbWxuICAgIDJtbG4gICAgMTBtbG4gICAxMDBtbG4KICAgcHJpbnQgKGxlbmd0aCAocHJpbWVzVG9VQSB4KSkgICAtLSAgIDAuMDEgICAgMC4wMiAgICAgMC4wOSAgICAgMS4yNiAgc2Vjb25kcw==

MTAwMDAwMDAw

100000000