RedHotChiliPepper

prefSums and mySieve .hs

Nov 28th, 2021 (edited)
498
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. prefSums ::  (Int->Int) -> Int -> [Int] -> UArray Int Int
  2. prefSums f n xs = runSTUArray $ do
  3.     arr <- newArray (0,n) 0
  4.  
  5.     forM_ xs $ \el -> do
  6.         old <- readArray arr el
  7.         writeArray arr el $ old + f el
  8.  
  9.     forM_ [1..n] $ \i -> do
  10.         pred <- readArray arr (i-1)
  11.         cur <- readArray arr i
  12.         writeArray arr i (pred+cur)
  13.     return arr
  14.  
  15. getOnSeg :: UArray Int Int -> Int -> Int -> Int
  16. getOnSeg arr l r = (arr ! r') - pref
  17.    where l' = min l maxn
  18.           r' = min r maxn
  19.          pref = if l' == 0 then 0 else arr ! (l'-1)
  20.  
  21. mySieve :: UArray Int Int
  22.        mySieve = runSTUArray $ do
  23.            primes <- (newArray (0,maxn) False)::ST s (STUArray s Int Bool)
  24.            megs <- newArray (0,maxn) intINF
  25.            
  26.            forM_ [2..maxn] $ \i -> do
  27.                fl <- readArray primes i
  28.                when (not fl) $ do
  29.                    forM_ [i,2*i..maxn] $ \j -> do
  30.                        writeArray primes j True
  31.                    writeArray megs i (getNodP i)
RAW Paste Data