IntMap instead Map, Int instead Integer

10.hs

import Data.List

import Data.IntMap (IntMap, (!))
import qualified Data.IntMap as IntMap

p :: Int -> Int
p n = (sieve (IntMap.fromList [(i, i * (i + 1) `div` 2 - 1) | i <- vs]) 2 r vs) ! n
               where vs = [n `div` i | i <- [1..r]] ++ reverse [1..n `div` r - 1]
                     r  = floor (sqrt (fromIntegral n))

sieve :: IntMap Int -> Int -> Int -> [Int] -> IntMap Int
sieve m p r vs | p > r     = m
               | otherwise = sieve (if m ! p > m ! (p - 1) then update m vs p else m) (p + 1) r vs

update :: IntMap Int -> [Int] -> Int -> IntMap Int
update m vs p = foldl' decrease m (map (\v -> (v, sumOfsieved m v p)) (takeWhile (>= p*p) vs))

decrease :: IntMap Int -> (Int, Int) -> IntMap Int
decrease m (k, vs) = IntMap.insertWith (flip (-)) k vs m

sumOfsieved :: IntMap Int -> Int -> Int -> Int
sumOfsieved m v p = p * (m ! (v `div` p) - m ! (p - 1))

main = print $ p $ 2*10^9

-- $ ghc -O2 10.hs
-- $ time ./10
-- 95673602693282040

-- real	0m5.062s
-- user	0m4.666s
-- sys	0m0.374s

10.prof

	Thu Jun  8 20:09 2017 Time and Allocation Profiling Report  (Final)

	   10 +RTS -p -h -RTS

	total time  =        4.89 secs   (4895 ticks @ 1000 us, 1 processor)
	total alloc = 7,790,156,216 bytes  (excludes profiling overheads)

COST CENTRE MODULE  %time %alloc

decrease    Main     49.5   79.2
sumOfsieved Main     33.3    5.7
update      Main     14.6   13.5
p           Main      1.1    1.3


                                                             individual     inherited
COST CENTRE        MODULE                  no.     entries  %time %alloc   %time %alloc

MAIN               MAIN                     46           0    0.0    0.0   100.0  100.0
 CAF               Main                     91           0    0.0    0.0   100.0  100.0
  main             Main                     92           1    0.0    0.0   100.0  100.0
   p               Main                     93           1    1.1    1.3   100.0  100.0
    p.vs           Main                     96           1    0.1    0.2     0.1    0.2
    p.r            Main                     95           1    0.0    0.0     0.0    0.0
    sieve          Main                     94       44721    0.9    0.1    98.8   98.5
     update        Main                     97        4648   14.6   13.5    97.9   98.4
      update.\     Main                     99     5038941    0.4    0.0    33.7    5.7
       sumOfsieved Main                    100     1921602   33.3    5.7    33.3    5.7
      decrease     Main                     98     5038941   49.5   79.2    49.5   79.2
 CAF               GHC.IO.Handle.FD         85           0    0.0    0.0     0.0    0.0
 CAF               GHC.Conc.Signal          82           0    0.0    0.0     0.0    0.0
 CAF               GHC.IO.Encoding          77           0    0.0    0.0     0.0    0.0
 CAF               GHC.IO.Encoding.Iconv    67           0    0.0    0.0     0.0    0.0