import Control.Monad (forM_, when)
import Control.Monad.ST
import Data.Array.ST
import Data.Array.Unboxed
 
sieve :: Int -> UArray Int Bool
sieve n = runSTUArray $ do
    let m = (n-1) `div` 2
        r = floor . sqrt $ fromIntegral n
    bits <- newArray (0, m-1) True
    forM_ [0 .. r `div` 2 - 1] $ \i -> do
        isPrime <- readArray bits i
        when isPrime $ do
            forM_ [2*i*i+6*i+3, 2*i*i+8*i+6 .. (m-1)] $ \j -> do
                writeArray bits j False
    return bits
 
primes :: Int -> [Int]
primes n = 2 : [2*i+3 | (i, True) <- assocs $ sieve n]
 
main = do
    print $ primes 100
    print $ sum $ primes 2000000

aW1wb3J0IENvbnRyb2wuTW9uYWQgKGZvck1fLCB3aGVuKQppbXBvcnQgQ29udHJvbC5Nb25hZC5TVAppbXBvcnQgRGF0YS5BcnJheS5TVAppbXBvcnQgRGF0YS5BcnJheS5VbmJveGVkCiAKc2lldmUgOjogSW50IC0+IFVBcnJheSBJbnQgQm9vbApzaWV2ZSBuID0gcnVuU1RVQXJyYXkgJCBkbwogICAgbGV0IG0gPSAobi0xKSBgZGl2YCAyCiAgICAgICAgciA9IGZsb29yIC4gc3FydCAkIGZyb21JbnRlZ3JhbCBuCiAgICBiaXRzIDwtIG5ld0FycmF5ICgwLCBtLTEpIFRydWUKICAgIGZvck1fIFswIC4uIHIgYGRpdmAgMiAtIDFdICQgXGkgLT4gZG8KICAgICAgICBpc1ByaW1lIDwtIHJlYWRBcnJheSBiaXRzIGkKICAgICAgICB3aGVuIGlzUHJpbWUgJCBkbwogICAgICAgICAgICBmb3JNXyBbMippKmkrNippKzMsIDIqaSppKzgqaSs2IC4uIChtLTEpXSAkIFxqIC0+IGRvCiAgICAgICAgICAgICAgICB3cml0ZUFycmF5IGJpdHMgaiBGYWxzZQogICAgcmV0dXJuIGJpdHMKIApwcmltZXMgOjogSW50IC0+IFtJbnRdCnByaW1lcyBuID0gMiA6IFsyKmkrMyB8IChpLCBUcnVlKSA8LSBhc3NvY3MgJCBzaWV2ZSBuXQoKbWFpbiA9IGRvCiAgICBwcmludCAkIHByaW1lcyAxMDAKICAgIHByaW50ICQgc3VtICQgcHJpbWVzIDIwMDAwMDA=