Skip to content

Instantly share code, notes, and snippets.

@nagat01

nagat01/sieve_intmap.hs

Created February 22, 2015 05:41
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save nagat01/718017c507a8c14cc46b to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save nagat01/718017c507a8c14cc46b to your computer and use it in GitHub Desktop.
Download ZIP
Raw
sieve_intmap.hs
{-# LANGUAGE ScopedTypeVariables #-}
import qualified Data.IntSet as Set
import Data.List(foldl')
sieve n = step [2] (Set.fromList [3, 5 .. n])
where
step ps cs =
case Set.minView cs of
Just (p, cs) ->
step (p:ps) $ foldl' (\cs x -> Set.delete x cs) cs [p, p * 2 .. n]
Nothing -> ps
main = print $ head $ sieve 10000000
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment