{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE MonoLocalBinds #-}
import Control.Monad (forM_, when)
import Control.Monad.ST     -- by stackoverflow.com/users/849891/will-ness 
import Control.Arrow        -- based on Daniel Fischer's code from
import Data.Array.ST        --   stackoverflow.com/a/15026238/849891
import Data.Array.Unboxed   -- here changed to work with odds only
import Data.Array.Base

primeSieve :: Int -> UArray Int Bool
primeSieve top = runSTUArray $ do
    let m = (top-1) `div` 2
    a <- newArray (0,m) True                 -- one extra at start: '1'
    let r = (`div` 2) . floor . sqrt $ fromIntegral top + 1
        mark step idx
            | m < idx = return ()
            | otherwise = do
                unsafeWrite a idx False  -- unsafe: idx from start
                mark step (idx+step)
        sift i
            | r < i     = return a   -- ((2*i+1)^2-1)`div`2 = 2*i*(i+1)
            | otherwise = do
                prim <- unsafeRead a i
                when prim $ mark (2*i+1) (2*i*(i+1))
                sift (i+1)
    sift 1

-- Return primes from sieve as list:
primesTo :: Int -> [Int]
primesTo top = 2 : drop 1 [2*p + 1 | (p,True) <- assocs $ primeSieve top]

main :: IO ()
 -- print . ( length &&& last) $ primesTo 20000000 
main  = do                   
  let a = primeSieve 2050000000
      (0,t) = bounds a       
      x = (+1).(*2).head.filter (a!) $ [t,t-1..1]   -- top prime
      n = length [ () | (p,True) <- assocs a]
  print (n, x)   
  
-- see also: ideone.com/0DfTcI, ideone.com/ltpuCC,
--   stackoverflow.com/questions/15024067/whats-the-ideal
--    -implementation-for-the-sieve-of-eratosthenes-between-lists-arr
{-
           this,STUA/odds: j24jxV             rhj9ub.SA()     fapob(C++)
 (1270607,19999999)     0.19s-8.3M
 (6000001,104395303)    1.28s-9.4M            7.54s-9.4M     0.79s-2.7M (1.6x)
 (8000000,141650939)    1.79s-9.4M   n^1.17   10.61-9.3M     1.11s-2.7M (1.6x)
 (18000000,334214459)   4.76s-9.3M   n^1.21         (5.9x)   2.89s-2.7M (1.6x)
           1bln                                              9.45s-2.7M 
           
2018-06-15:               j24jxV           (KwZNc)             fapob
   1.5x slower       6m-0.40s- 9.3M      (2.63s-10MB)        0.27s- 8.9MB
   1.6x slower      18m-1.79s-23.2M      (9.69s-24MB)        1.11s-22.9MB
   1.55x     100556393-12.43s-128M                           7.96s-128M
  than C++                      (6.5..5.5x slower than j24jxV)
-}