Eratosthenes' sieve in Haskell and Data.Map.Map

pqsieve.cpp

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

int main(int argc, char **argv) {
    priority_queue<pair<int,int> > pq;
    printf("%d\n", 2);
    pq.push(make_pair(-4, 2));
    for(int i = 2; i < 100; ) {
        int x = -pq.top().first;
        int q = pq.top().second;
        pq.pop();
        if(x-i==2) {
            int p = i+1;
            printf("%d\n", p);
            pq.push(make_pair(-p*p, p));
        }
        pq.push(make_pair(-x-q, q));
        i = x;
    }
    return 0;
}

sieve.hs

import qualified Data.Map

sieve :: (Data.Map.Map Int [Int], Int) -> [Int]
sieve (m,i) =
        let v = Data.Map.lookup i m
        in case v of
              Nothing -> i : sieve (Data.Map.insert (i*i) [i] m,i+1)
              Just l -> sieve (foldl f m l, i+1)
        where
              f mm p = Data.Map.insertWith' (++) (i+p) [p] m

primes = sieve (Data.Map.empty, 2)

main :: IO ()
main = do
        putStrLn $ show $ primes !! 9999999