links

< home >
< unix stuff >
< code >
< writing >
< archive >
< music >
< photos >
< recipes >
< site map >
< about badcomputer >

sieve of eratosthenes

haskell

{- Sieve of Erastosthenes in Haskell
 - Written by Robert Hoelz
 -}

import qualified Data.Map as Map
import System.Environment (getArgs)

main :: IO ()
main = do
    args <- getArgs
    let limit = (read :: String -> Integer) (head args)
    printMap (removeNonPrimes 2 (buildSieves limit) limit)
    putStrLn ""

buildSieves :: (Num a, Ord a) => a -> Map.Map a a
buildSieves limit
            | limit < 2 = Map.singleton 0 0
            | limit == 2 = Map.singleton 2 1
            | otherwise = buildSievesAux (limit - 1) (Map.singleton limit 1)

buildSievesAux :: (Num a, Ord a) => a -> Map.Map a a -> Map.Map a a
buildSievesAux 1 map = map
buildSievesAux limit map =
    let newMap = Map.insert limit 1 map
        in
            newMap `seq` buildSievesAux (limit - 1) newMap

printMap :: Show a => Map.Map a b -> IO ()
printMap sieves = printMapAux (Map.keys sieves)

printMapAux :: Show a => [a] -> IO ()
printMapAux [] = return ()
printMapAux (x:xs) = do
    putStr ((show x) ++ " ")
    printMapAux xs

removeMultiples :: (Num a, Ord a) => Map.Map a b -> a -> a -> Map.Map a b
removeMultiples sieves num limit =
    removeMultiplesAux sieves num 2 limit

removeMultiplesAux :: (Num a, Ord a) => Map.Map a b -> a -> a -> a -> Map.Map a b
removeMultiplesAux sieves num multiplier limit =
    let multiple = num * multiplier
        in
            if multiple > limit
                then
                    sieves
                else
                    let newMap = Map.delete multiple sieves
                        in
                            newMap `seq` removeMultiplesAux newMap num (multiplier + 1) limit

removeNonPrimes :: (Num a, Ord a) => a -> Map.Map a b -> a -> Map.Map a b
removeNonPrimes start sieves limit =
    if (start * start) > limit
        then
            sieves
        else
            let stripped = removeMultiples sieves start limit
                in removeNonPrimes (nextPrime stripped start) stripped limit

nextPrime :: (Eq a, Num a) => Map.Map a b -> a -> a
nextPrime sieves num = nextPrimeAux (Map.keys sieves) num

nextPrimeAux :: (Eq a, Num a) => [a] -> a -> a
nextPrimeAux [] num = 1
nextPrimeAux (x:xs) num =
    if x == num
        then
            head xs
        else
            nextPrimeAux xs num

back to Eratosthenes page

stats

It is Friday August 29, 2008 12:44 am
This page served 752 times
This page last modified: April 14, 2008 11:28 am
Your IP address is: 38.103.63.61
You are browsing using: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)
You are browsing from: United States.
badcomputer.org's uptime: 00:44:01 up 29 days, 15:50, 2 users, load average: 0.02, 0.03, 0.00