[Tutor] primes

[Sean Perry]

Pierre Barbier de Reuille wrote:
> 
> def sieve( max ):
>   max_val = int( sqrt( max ) )
>   s = Set(xrange( 4, max, 2 ))
>   for i in xrange( 3, max_val, 2 ):
>     s.update( xrange( 2*i, max, i ) )
>   return [ i for i in xrange( 2, max ) if i not in s ]
> 

just for grins, here is the same (mostly) code in haskell

import Data.Set(elems, fromList, member, union)

primeSieve :: Int -> [Int]
primeSieve n = [ prime | prime <- [ 2 .. n ], not $ prime `member` 
nonPrimes ]
   where
     evenSet         = fromList [4, 6 .. n ]
     xIncrements x   = [ 2 * x, (2 * x) + x .. n ]
     maxVal          = floor . sqrt $ fromIntegral n
     oddSet          = fromList . concat $ map xIncrements [ 3, 5 .. 
maxVal ]
     nonPrimes       = union evenSet oddSet

fromList makes a list into a Set. [ x | x <- y, pred ] is analogous to 
Python's [ x for x in y if pred x ]. The '$' operator removes the need 
for parens.

foo $ bar baz --> foo (bar baz)

oh and '.' is the function composition operator.