エラトステネスの篩 （ Haskell, Data.Vector 版 ）

エラトステネスの篩のアルゴリズムを使って素数のリストを返す関数を作ってみました。

Ruby や Scheme の時と同じように配列をバリバリ使いたかったので、Data.Vector を利用しました。
「求める素数の上限を決めなくてはならない」という制限はありますが、一億以下の素数を 5 秒たらずで求められるので、高速な方だと思います。
　

primeList.hs

import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM
import Control.Monad.ST
import Control.Monad

--
-- エラトステネスの篩による素数リスト
--
-- * ex : primeList 20  =>  [2,3,5,7,11,13,17,19]
--
primeList :: Int -> [Int]
primeList n = 2 : (map indexToValue $ U.toList $ U.elemIndices True $ sieve)
  where
    indexToValue i = 2 * i + 3
    valueToIndex v = div (v - 3) 2
    lastIndex      = valueToIndex n

    sieve = runST $ do
      mVec <- UM.replicate (lastIndex + 1) True
      mapM_ (loop mVec) [0 .. valueToIndex (floor $ sqrt $ fromIntegral n)]
      U.unsafeFreeze mVec

    loop vec i = do
      v <- UM.unsafeRead vec i
      when v $ do
        let (s, d) = (2 * i * (i + 3) + 3, indexToValue i)
        mapM_ setFalse [s, s + d .. lastIndex]
          where setFalse i = UM.unsafeWrite vec i False




main :: IO ()
main = print $ last $ primeList 100000000

>primeList +RTS -sstderr
primeList +RTS -sstderr
99999989
   4,902,213,164 bytes allocated in the heap
         393,184 bytes copied during GC
      50,026,280 bytes maximum residency (3 sample(s))
         342,232 bytes maximum slop
              49 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0      9289 colls,     0 par    0.11s    0.07s     0.0000s    0.0021s
  Gen  1         3 colls,     0 par    0.00s    0.01s     0.0017s    0.0049s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    4.29s  (  4.86s elapsed)
  GC      time    0.11s  (  0.08s elapsed)
  EXIT    time    0.00s  (  0.01s elapsed)
  Total   time    4.40s  (  4.94s elapsed)

  %GC     time       2.5%  (1.6% elapsed)

  Alloc rate    1,142,699,706 bytes per MUT second

  Productivity  97.5% of total user, 86.8% of total elapsed

他の関数と一緒に GitHub で公開しています。