Control.Monad.Reader

Everything About Mathematics, Functional Programming, and Haskell

Sieve of Eratosthenes In Haskell

leave a comment »

Algorithm description, see Sieve of Eratosthenes

module Main where

import System.Environment

isPrime p (x:xs)
	| x*x > p	 = True
	| p `mod` x == 0 = False
	| otherwise	 = isPrime p xs

primes = 2 : oprimes
	where oprimes = 3 : [ p | p <- [5,7..], isPrime p oprimes]

main = do
	args <- getArgs
	let	n = read $ args !! 0
		x = takeWhile (< n) primes
	print $ length x
	print x

There is a HackageDB package called primes which provides an efficient lazy wheel sieve for prime generation.

This version looks nicer, but less effective:

sieve (x:xs) = x : sieve xs'
	where xs' = filter (\y -> y `mod` x /= 0) xs

primes = 2 : sieve [3,5..]

See also The Genuine Sieve of Eratosthenes

Advertisements

Written by Lee Duhem

May 20, 2009 at 5:12 pm

Posted in Algorithm, Haskell, Mathematics

Tagged with , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: