{-# 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)
-}

ey0jIE9QVElPTlNfR0hDIC1PMiAjLX0Key0jIExBTkdVQUdFIE1vbm9Mb2NhbEJpbmRzICMtfQppbXBvcnQgQ29udHJvbC5Nb25hZCAoZm9yTV8sIHdoZW4pCmltcG9ydCBDb250cm9sLk1vbmFkLlNUICAgICAtLSBieSBzdGFja292ZXJmbG93LmNvbS91c2Vycy84NDk4OTEvd2lsbC1uZXNzIAppbXBvcnQgQ29udHJvbC5BcnJvdyAgICAgICAgLS0gYmFzZWQgb24gRGFuaWVsIEZpc2NoZXIncyBjb2RlIGZyb20KaW1wb3J0IERhdGEuQXJyYXkuU1QgICAgICAgIC0tICAgc3RhY2tvdmVyZmxvdy5jb20vYS8xNTAyNjIzOC84NDk4OTEKaW1wb3J0IERhdGEuQXJyYXkuVW5ib3hlZCAgIC0tIGhlcmUgY2hhbmdlZCB0byB3b3JrIHdpdGggb2RkcyBvbmx5CmltcG9ydCBEYXRhLkFycmF5LkJhc2UKCnByaW1lU2lldmUgOjogSW50IC0+IFVBcnJheSBJbnQgQm9vbApwcmltZVNpZXZlIHRvcCA9IHJ1blNUVUFycmF5ICQgZG8KICAgIGxldCBtID0gKHRvcC0xKSBgZGl2YCAyCiAgICBhIDwtIG5ld0FycmF5ICgwLG0pIFRydWUgICAgICAgICAgICAgICAgIC0tIG9uZSBleHRyYSBhdCBzdGFydDogJzEnCiAgICBsZXQgciA9IChgZGl2YCAyKSAuIGZsb29yIC4gc3FydCAkIGZyb21JbnRlZ3JhbCB0b3AgKyAxCiAgICAgICAgbWFyayBzdGVwIGlkeAogICAgICAgICAgICB8IG0gPCBpZHggPSByZXR1cm4gKCkKICAgICAgICAgICAgfCBvdGhlcndpc2UgPSBkbwogICAgICAgICAgICAgICAgdW5zYWZlV3JpdGUgYSBpZHggRmFsc2UgIC0tIHVuc2FmZTogaWR4IGZyb20gc3RhcnQKICAgICAgICAgICAgICAgIG1hcmsgc3RlcCAoaWR4K3N0ZXApCiAgICAgICAgc2lmdCBpCiAgICAgICAgICAgIHwgciA8IGkgICAgID0gcmV0dXJuIGEgICAtLSAoKDIqaSsxKV4yLTEpYGRpdmAyID0gMippKihpKzEpCiAgICAgICAgICAgIHwgb3RoZXJ3aXNlID0gZG8KICAgICAgICAgICAgICAgIHByaW0gPC0gdW5zYWZlUmVhZCBhIGkKICAgICAgICAgICAgICAgIHdoZW4gcHJpbSAkIG1hcmsgKDIqaSsxKSAoMippKihpKzEpKQogICAgICAgICAgICAgICAgc2lmdCAoaSsxKQogICAgc2lmdCAxCgotLSBSZXR1cm4gcHJpbWVzIGZyb20gc2lldmUgYXMgbGlzdDoKcHJpbWVzVG8gOjogSW50IC0+IFtJbnRdCnByaW1lc1RvIHRvcCA9IDIgOiBkcm9wIDEgWzIqcCArIDEgfCAocCxUcnVlKSA8LSBhc3NvY3MgJCBwcmltZVNpZXZlIHRvcF0KCm1haW4gOjogSU8gKCkKIC0tIHByaW50IC4gKCBsZW5ndGggJiYmIGxhc3QpICQgcHJpbWVzVG8gMjAwMDAwMDAgCm1haW4gID0gZG8gICAgICAgICAgICAgICAgICAgCiAgbGV0IGEgPSBwcmltZVNpZXZlIDIwNTAwMDAwMDAKICAgICAgKDAsdCkgPSBib3VuZHMgYSAgICAgICAKICAgICAgeCA9ICgrMSkuKCoyKS5oZWFkLmZpbHRlciAoYSEpICQgW3QsdC0xLi4xXSAgIC0tIHRvcCBwcmltZQogICAgICBuID0gbGVuZ3RoIFsgKCkgfCAocCxUcnVlKSA8LSBhc3NvY3MgYV0KICBwcmludCAobiwgeCkgICAKICAKLS0gc2VlIGFsc286IGlkZW9uZS5jb20vMERmVGNJLCBpZGVvbmUuY29tL2x0cHVDQywKLS0gICBzdGFja292ZXJmbG93LmNvbS9xdWVzdGlvbnMvMTUwMjQwNjcvd2hhdHMtdGhlLWlkZWFsCi0tICAgIC1pbXBsZW1lbnRhdGlvbi1mb3ItdGhlLXNpZXZlLW9mLWVyYXRvc3RoZW5lcy1iZXR3ZWVuLWxpc3RzLWFycgp7LQogICAgICAgICAgIHRoaXMsU1RVQS9vZGRzOiBqMjRqeFYgICAgICAgICAgICAgcmhqOXViLlNBKCkgICAgIGZhcG9iKEMrKykKICgxMjcwNjA3LDE5OTk5OTk5KSAgICAgMC4xOXMtOC4zTQogKDYwMDAwMDEsMTA0Mzk1MzAzKSAgICAxLjI4cy05LjRNICAgICAgICAgICAgNy41NHMtOS40TSAgICAgMC43OXMtMi43TSAoMS42eCkKICg4MDAwMDAwLDE0MTY1MDkzOSkgICAgMS43OXMtOS40TSAgIG5eMS4xNyAgIDEwLjYxLTkuM00gICAgIDEuMTFzLTIuN00gKDEuNngpCiAoMTgwMDAwMDAsMzM0MjE0NDU5KSAgIDQuNzZzLTkuM00gICBuXjEuMjEgICAgICAgICAoNS45eCkgICAyLjg5cy0yLjdNICgxLjZ4KQogICAgICAgICAgIDFibG4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgOS40NXMtMi43TSAKICAgICAgICAgICAKMjAxOC0wNi0xNTogICAgICAgICAgICAgICBqMjRqeFYgICAgICAgICAgIChLd1pOYykgICAgICAgICAgICAgZmFwb2IKICAgMS41eCBzbG93ZXIgICAgICAgNm0tMC40MHMtIDkuM00gICAgICAoMi42M3MtMTBNQikgICAgICAgIDAuMjdzLSA4LjlNQgogICAxLjZ4IHNsb3dlciAgICAgIDE4bS0xLjc5cy0yMy4yTSAgICAgICg5LjY5cy0yNE1CKSAgICAgICAgMS4xMXMtMjIuOU1CCiAgIDEuNTV4ICAgICAxMDA1NTYzOTMtMTIuNDNzLTEyOE0gICAgICAgICAgICAgICAgICAgICAgICAgICA3Ljk2cy0xMjhNCiAgdGhhbiBDKysgICAgICAgICAgICAgICAgICAgICAgKDYuNS4uNS41eCBzbG93ZXIgdGhhbiBqMjRqeFYpCi19