-- from http://w...content-available-to-author-only...l.org/haskellwiki/Prime_numbers#Using_ST_Array
 
{-# OPTIONS -O2 -optc-O3 #-}
import Control.Monad
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
 
sieveUA :: Int -> UArray Int Bool
sieveUA top = runSTUArray $ do
    let m = (top-1) `div` 2
        r = floor . sqrt $ fromIntegral top + 1
    sieve <- newArray (1,m) True      -- :: ST s (STUArray s Int Bool)
    forM_ [1..r `div` 2] $ \i -> do
      isPrime <- readArray sieve i
      when isPrime $ do               -- ((2*i+1)^2-1)`div`2 == 2*i*(i+1)
        forM_ [2*i*(i+1), 2*i*(i+2)+1..m] $ \j -> do
          writeArray sieve j False
    return sieve
 
primesToUA :: Int -> [Int]
primesToUA top | top > 1 = 2 : [2*p + 1 | (p,True) <- assocs $ sieveUA top]
               | otherwise = []               
 
main = do 
   x <- read `fmap` getLine      --   1mln    2mln    10mln   100mln
   print (last (primesToUA x))   --   0.05    0.10     0.56     6.61  seconds

LS0gZnJvbSBodHRwOi8vdy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4ubC5vcmcvaGFza2VsbHdpa2kvUHJpbWVfbnVtYmVycyNVc2luZ19TVF9BcnJheQoKey0jIE9QVElPTlMgLU8yIC1vcHRjLU8zICMtfQppbXBvcnQgQ29udHJvbC5Nb25hZAppbXBvcnQgQ29udHJvbC5Nb25hZC5TVAppbXBvcnQgRGF0YS5BcnJheS5TVAppbXBvcnQgRGF0YS5BcnJheS5VbmJveGVkCiAKc2lldmVVQSA6OiBJbnQgLT4gVUFycmF5IEludCBCb29sCnNpZXZlVUEgdG9wID0gcnVuU1RVQXJyYXkgJCBkbwogICAgbGV0IG0gPSAodG9wLTEpIGBkaXZgIDIKICAgICAgICByID0gZmxvb3IgLiBzcXJ0ICQgZnJvbUludGVncmFsIHRvcCArIDEKICAgIHNpZXZlIDwtIG5ld0FycmF5ICgxLG0pIFRydWUgICAgICAtLSA6OiBTVCBzIChTVFVBcnJheSBzIEludCBCb29sKQogICAgZm9yTV8gWzEuLnIgYGRpdmAgMl0gJCBcaSAtPiBkbwogICAgICBpc1ByaW1lIDwtIHJlYWRBcnJheSBzaWV2ZSBpCiAgICAgIHdoZW4gaXNQcmltZSAkIGRvICAgICAgICAgICAgICAgLS0gKCgyKmkrMSleMi0xKWBkaXZgMiA9PSAyKmkqKGkrMSkKICAgICAgICBmb3JNXyBbMippKihpKzEpLCAyKmkqKGkrMikrMS4ubV0gJCBcaiAtPiBkbwogICAgICAgICAgd3JpdGVBcnJheSBzaWV2ZSBqIEZhbHNlCiAgICByZXR1cm4gc2lldmUKIApwcmltZXNUb1VBIDo6IEludCAtPiBbSW50XQpwcmltZXNUb1VBIHRvcCB8IHRvcCA+IDEgPSAyIDogWzIqcCArIDEgfCAocCxUcnVlKSA8LSBhc3NvY3MgJCBzaWV2ZVVBIHRvcF0KICAgICAgICAgICAgICAgfCBvdGhlcndpc2UgPSBbXSAgICAgICAgICAgICAgIAogCm1haW4gPSBkbyAKICAgeCA8LSByZWFkIGBmbWFwYCBnZXRMaW5lICAgICAgLS0gICAxbWxuICAgIDJtbG4gICAgMTBtbG4gICAxMDBtbG4KICAgcHJpbnQgKGxhc3QgKHByaW1lc1RvVUEgeCkpICAgLS0gICAwLjA1ICAgIDAuMTAgICAgIDAuNTYgICAgIDYuNjEgIHNlY29uZHM=

MTAwMDAwMDAw

100000000