-- from http://w...content-available-to-author-only...l.org/haskellwiki/Prime_numbers#Using_ST_Array
{-# OPTIONS -O2 -optc-O3 #-}
import Data.Word
import Data.Array.ST
import Data.Array.Unboxed
import Data.Array.Base
primesToUA :: Word32-> [Word32]
primesToUA top = do
let sieveUA top = runSTUArray $ do
buf <- newArray (0,m) True -- :: ST s (STUArray s Int Bool)
let cullUA i = do
let p = i + i + 3
strt = p * (i + 1) + i
let cull j = do
if j > m then cullUA (i + 1)
else do
unsafeWrite buf j False
cull (j + p)
else do
e <- unsafeRead buf i
if e then cull strt else cullUA (i + 1)
if top
> 1 then 2 :
[2 * (fromIntegral i
) + 3 | (i
,True
) <- assocs
$ sieveUA top
] else []
main = do
print (length (primesToUA x
)) -- 0.01 0.02 0.09 1.26 seconds
LS0gZnJvbSBodHRwOi8vdy4uLmNvbnRlbnQtYXZhaWxhYmxlLXRvLWF1dGhvci1vbmx5Li4ubC5vcmcvaGFza2VsbHdpa2kvUHJpbWVfbnVtYmVycyNVc2luZ19TVF9BcnJheQoKey0jIE9QVElPTlMgLU8yIC1vcHRjLU8zICMtfQppbXBvcnQgRGF0YS5Xb3JkCmltcG9ydCBDb250cm9sLk1vbmFkCmltcG9ydCBDb250cm9sLk1vbmFkLlNUCmltcG9ydCBEYXRhLkFycmF5LlNUCmltcG9ydCBEYXRhLkFycmF5LlVuYm94ZWQKaW1wb3J0IERhdGEuQXJyYXkuQmFzZQoKcHJpbWVzVG9VQSA6OiBXb3JkMzItPiBbV29yZDMyXQpwcmltZXNUb1VBIHRvcCA9IGRvCiAgICBsZXQgc2lldmVVQSB0b3AgPSBydW5TVFVBcnJheSAkIGRvICAgIAogICAgICAgIGxldCBtID0gKChmcm9tSW50ZWdyYWwgdG9wKSAtIDMpIGBkaXZgIDIgOjogSW50CiAgICAgICAgYnVmIDwtIG5ld0FycmF5ICgwLG0pIFRydWUgLS0gOjogU1QgcyAoU1RVQXJyYXkgcyBJbnQgQm9vbCkKICAgICAgICBsZXQgY3VsbFVBIGkgPSBkbwogICAgICAgICAgICBsZXQgcCA9IGkgKyBpICsgMwogICAgICAgICAgICAgICAgc3RydCA9IHAgKiAoaSArIDEpICsgaQogICAgICAgICAgICBsZXQgY3VsbCBqID0gZG8KICAgICAgICAgICAgICAgIGlmIGogPiBtIHRoZW4gY3VsbFVBIChpICsgMSkKICAgICAgICAgICAgICAgIGVsc2UgZG8KICAgICAgICAgICAgICAgICAgICB1bnNhZmVXcml0ZSBidWYgaiBGYWxzZQogICAgICAgICAgICAgICAgICAgIGN1bGwgKGogKyBwKQogICAgICAgICAgICBpZiBzdHJ0ID4gbSB0aGVuIHJldHVybiAoKQoJICAgICAgICBlbHNlIGRvCgkgICAgICAgICAgICBlIDwtIHVuc2FmZVJlYWQgYnVmIGkKCSAgICAgICAgICAgIGlmIGUgdGhlbiBjdWxsIHN0cnQgZWxzZSBjdWxsVUEgKGkgKyAxKQogICAgICAgIGN1bGxVQSAwOyByZXR1cm4gYnVmCiAgICBpZiB0b3AgPiAxIHRoZW4gMiA6IFsyICogKGZyb21JbnRlZ3JhbCBpKSArIDMgfCAoaSxUcnVlKSA8LSBhc3NvY3MgJCBzaWV2ZVVBIHRvcF0KICAgIGVsc2UgW10KCm1haW4gPSBkbyAKICAgeCA8LSByZWFkIGBmbWFwYCBnZXRMaW5lICAgICAgLS0gICAxbWxuICAgIDJtbG4gICAgMTBtbG4gICAxMDBtbG4KICAgcHJpbnQgKGxlbmd0aCAocHJpbWVzVG9VQSB4KSkgICAtLSAgIDAuMDEgICAgMC4wMiAgICAgMC4wOSAgICAgMS4yNiAgc2Vjb25kcw==