{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE MonoLocalBinds #-}
import Control.Monad (forM_, when)
import Control.Monad.ST
import Control.Arrow       -- based on Daniel Fischer's code from
import Data.Array.ST       --   stackoverflow.com/a/15026238/849891
import Data.Array.Unboxed
import Data.Array.Base
 
primeSieve :: Int -> UArray Int Bool
primeSieve top = runSTUArray $ do
    a <- newArray (0,top) True              -- two extra at start: '0', '1'
    let r = ceiling . sqrt $ fromIntegral top
        mark step idx
            | top < idx = return ()
            | otherwise = do
                unsafeWrite a idx False      -- unsafe: idx from start
                mark step (idx+step)
        sift p
            | r < p     = return a
            | otherwise = do
                prim <- unsafeRead a p
                when prim $ mark (2*p) (p*p)
                sift (p+2)
    mark 2 4
    sift 3
 
-- Return primes from sieve as list:
primesTo :: Int -> [Int]
primesTo top = drop 2 [p | (p,True) <- assocs $ primeSieve top]
 
main :: IO ()
main1 = print . ( length &&& last) $ primesTo 20000000     -- 10mln: x=9999991   0.09s-7.7M 
-- main = print . ( last) $ primesTo 20000000              --        n=664579    0.17s-7.8M   list:0.27-30.3
 
main  = do                                                 -- 20mln: x=19999999  0.20s-8.8M 
  let a = primeSieve 104395305                             --        n=1270607   0.37s-8.8M   list:0.54-38.4
      (0,t) = bounds a
      p = head   [idx | idx <- [t,t-1..2], a!idx]          -- top prime
      n = length [ () | (p,True) <- assocs a] - 2
  print (n, p)                                     -- see also: ideone.com/j24jxV
{- Success	 time: 2.55 memory: 9304 signal:0
   (6000001,104395303) -}

ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0Key0jIExBTkdVQUdFIE1vbm9Mb2NhbEJpbmRzICMtfQppbXBvcnQgQ29udHJvbC5Nb25hZCAoZm9yTV8sIHdoZW4pCmltcG9ydCBDb250cm9sLk1vbmFkLlNUCmltcG9ydCBDb250cm9sLkFycm93ICAgICAgIC0tIGJhc2VkIG9uIERhbmllbCBGaXNjaGVyJ3MgY29kZSBmcm9tCmltcG9ydCBEYXRhLkFycmF5LlNUICAgICAgIC0tICAgc3RhY2tvdmVyZmxvdy5jb20vYS8xNTAyNjIzOC84NDk4OTEKaW1wb3J0IERhdGEuQXJyYXkuVW5ib3hlZAppbXBvcnQgRGF0YS5BcnJheS5CYXNlCgpwcmltZVNpZXZlIDo6IEludCAtPiBVQXJyYXkgSW50IEJvb2wKcHJpbWVTaWV2ZSB0b3AgPSBydW5TVFVBcnJheSAkIGRvCiAgICBhIDwtIG5ld0FycmF5ICgwLHRvcCkgVHJ1ZSAgICAgICAgICAgICAgLS0gdHdvIGV4dHJhIGF0IHN0YXJ0OiAnMCcsICcxJwogICAgbGV0IHIgPSBjZWlsaW5nIC4gc3FydCAkIGZyb21JbnRlZ3JhbCB0b3AKICAgICAgICBtYXJrIHN0ZXAgaWR4CiAgICAgICAgICAgIHwgdG9wIDwgaWR4ID0gcmV0dXJuICgpCiAgICAgICAgICAgIHwgb3RoZXJ3aXNlID0gZG8KICAgICAgICAgICAgICAgIHVuc2FmZVdyaXRlIGEgaWR4IEZhbHNlICAgICAgLS0gdW5zYWZlOiBpZHggZnJvbSBzdGFydAogICAgICAgICAgICAgICAgbWFyayBzdGVwIChpZHgrc3RlcCkKICAgICAgICBzaWZ0IHAKICAgICAgICAgICAgfCByIDwgcCAgICAgPSByZXR1cm4gYQogICAgICAgICAgICB8IG90aGVyd2lzZSA9IGRvCiAgICAgICAgICAgICAgICBwcmltIDwtIHVuc2FmZVJlYWQgYSBwCiAgICAgICAgICAgICAgICB3aGVuIHByaW0gJCBtYXJrICgyKnApIChwKnApCiAgICAgICAgICAgICAgICBzaWZ0IChwKzIpCiAgICBtYXJrIDIgNAogICAgc2lmdCAzCgotLSBSZXR1cm4gcHJpbWVzIGZyb20gc2lldmUgYXMgbGlzdDoKcHJpbWVzVG8gOjogSW50IC0+IFtJbnRdCnByaW1lc1RvIHRvcCA9IGRyb3AgMiBbcCB8IChwLFRydWUpIDwtIGFzc29jcyAkIHByaW1lU2lldmUgdG9wXQoKbWFpbiA6OiBJTyAoKQptYWluMSA9IHByaW50IC4gKCBsZW5ndGggJiYmIGxhc3QpICQgcHJpbWVzVG8gMjAwMDAwMDAgICAgIC0tIDEwbWxuOiB4PTk5OTk5OTEgICAwLjA5cy03LjdNIAotLSBtYWluID0gcHJpbnQgLiAoIGxhc3QpICQgcHJpbWVzVG8gMjAwMDAwMDAgICAgICAgICAgICAgIC0tICAgICAgICBuPTY2NDU3OSAgICAwLjE3cy03LjhNICAgbGlzdDowLjI3LTMwLjMKCm1haW4gID0gZG8gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLS0gMjBtbG46IHg9MTk5OTk5OTkgIDAuMjBzLTguOE0gCiAgbGV0IGEgPSBwcmltZVNpZXZlIDEwNDM5NTMwNSAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLS0gICAgICAgIG49MTI3MDYwNyAgIDAuMzdzLTguOE0gICBsaXN0OjAuNTQtMzguNAogICAgICAoMCx0KSA9IGJvdW5kcyBhCiAgICAgIHAgPSBoZWFkICAgW2lkeCB8IGlkeCA8LSBbdCx0LTEuLjJdLCBhIWlkeF0gICAgICAgICAgLS0gdG9wIHByaW1lCiAgICAgIG4gPSBsZW5ndGggWyAoKSB8IChwLFRydWUpIDwtIGFzc29jcyBhXSAtIDIKICBwcmludCAobiwgcCkgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgLS0gc2VlIGFsc286IGlkZW9uZS5jb20vajI0anhWCnstIFN1Y2Nlc3MJIHRpbWU6IDIuNTUgbWVtb3J5OiA5MzA0IHNpZ25hbDowCiAgICg2MDAwMDAxLDEwNDM5NTMwMykgLX0=